共有回帖数 0 个
-
template typename T
class SplayTree
{
public:
SplayTree();
~SplayTree();
void Delete(const T &x);
void Insert(const T &x);
const T &Max()
{
node *p = root;
while (p-rchild != nullnode)
p = p-rchild;
Splay(root, p-key);
return p-key;
}
const T &Min()
{
node *p = root;
while (p-lchild != nullnode)
p = p-lchild;
Splay(root, p-key);
return p-key;
}
private:
struct node
{
T key;
node *lchild, *rchild;
node() {}
node(const T &x) : key(x) {}
}*nullnode, *root;
void LeftRotate(node *&x);
void RightRotate(node *&x);
void Splay(node *&root, const T &x);
};
template typename T
SplayTreeT::SplayTree()
{
nullnode = new node;
nullnode-lchild = nullnode;
nullnode-rchild = nullnode;
root = nullnode;
}
template typename T
SplayTreeT::~SplayTree()
{
while (root != nullnode)
Delete(Max());
}
template typename T
void SplayTreeT::Delete(const T &x)
{
node *newroot;
Splay(root, x);
if (root-key != x)
return;
if (root-lchild == nullnode)
newroot = root-rchild;
else
{
newroot = root-lchild;
Splay(newroot, x);
newroot-rchild = root-rchild;
}
delete root;
root = newroot;
}
template typename T
void SplayTreeT::Insert(const T &x)
{
node *newnode = new node(x);
if (root == nullnode)
{
newnode-lchild = nullnode;
newnode-rchild = nullnode;
root = newnode;
return;
}
Splay(root, x);
if (x root-key)
{
newnode-lchild = root-lchild;
root-lchild = nullnode;
newnode-rchild = root;
root = newnode;
}
else
{
newnode-rchild = root-rchild;
root-rchild = nullnode;
newnode-lchild = root;
root = newnode;
}
}
template typename T
void SplayTreeT::LeftRotate(node *&x)
{
node *y = x-rchild;
x-rchild = y-lchild;
y-lchild = x;
x = y;
}
template typename T
void SplayTreeT::RightRotate(node *&x)
{
node *y = x-lchild;
x-lchild = y-rchild;
y-rchild = x;
x = y;
}
template typename T
void SplayTreeT::Splay(node *&root, const T &x)
{
node head, *ltree = &head, *rtree = &head;
head.lchild = nullnode;
head.rchild = nullnode;
while (x != root-key)
{
if (x root-key)
{
if (root-lchild != nullnode && x root-lchild-key)
RightRotate(root);
if (root-lchild == nullnode)
break;
rtree-lchild = root;
rtree = root;
root = root-lchild;
}
else
{
if (root-rchild != nullnode && root-rchild-key x)
LeftRotate(root);
if (root-rchild == nullnode)
break;
ltree-rchild = root;
ltree = root;
root = root-rchild;
}
}
ltree-rchild = root-lchild;
root-lchild = head.rchild;
rtree-lchild = root-rchild;
root-rchild = head.lchild;
}
Splay Tree（伸展树）是一种 Binary Search Tree（二叉搜索树），由 Daniel Sleator 和 Robert E. Tarjan 发明。单次操作可能会花费 O(n) 的时间，但 m 次操作的最坏情况下运行时间为 O(m*log2(n))。
Splay Tree 的基本思想是，当一个结点被访问后，通过一系列的旋转操作，使它成为整棵树的根。如果这个结点所处位置很深，那么根到该结点的路径上也会有很多较深的结点。经过一系列旋转，这些结点的深度将会减少，从而起到了平衡整棵树的效果。而且对于经常访问到的结点，它们的深度相对较小，访问它们的时间也较少。
自底向上旋转的 Splay Tree 一般有两种实现方法。一是为每个结点建立一个指向其父结点的指针，另一种是记录访问路径。然后从根往下搜索，再自底向上进行旋转。这种实现方式需要一定的空间，而且也需要处理各种情况。一种改进方式是将 Splay Tree 的旋转操作改为自顶向下进行，只需要 O(1) 的附加空间��
楼主 2016-06-09 09:21 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
