Splay Tree
程序员文章站
2022-04-24 23:53:34
...
Splay Tree的引入
类似于内存管理中的页面置换算法,在BST中最近被访问的节点,也更有可能在下一次被访问,为了利用这一局部性,Splay
Tree在每次访问一个节点后,都把这个节点提到根节点的位置,因此Splay Tree和其他BST的最大区别在于他的Search,
Insert,Remove算法都是动态的。
具体操作
双层伸展的精髓在于每次向上追溯两层,而非一层,反复考察祖孙三代v-p-g,根据他们的相对位置,经过两次旋转使得v
上升两层,成为子树根。
(1)zig-zag/zag-zig旋转和AVL树一样
(2)zig-zig/zag-zag与AVL略有差异
以前绕着p旋转,使得v提升一层,Splay Tree绕着g旋转,使得v提升一层,并且对应路径的长度降低了一半,Splay Tree的特点在于每次访问一个深节点时,都会把这个节点提到树根,并且把对应路径的长度减小一半,知错就改。
Splay Tree的算法
(1)Splay的实现
void AttachedAsLc(BinNodePosi(T)p,BinNodePosi(T)lc)
{
p->lc=lc;
if(lc)lc->parent=p;
}
void AttachedAsRc(BinNodePosi(T)p,BinNodePosi(T)rc)
{
p->rc=rc;
if(rc)rc->parent=p;
}
template<typename T>
BinNodePosi(T)Splay<T>::splay(BinNodePosi(T)v)
{
if(!v)return NULL;
BinNodePosi(T)p;
BinNodePosi(T)g;
while((p=v->parent)&&(g=p->parent))
{
BinNodePosi(T) gg=g->parent;
if(IsLChild(*v))
{
if(IsLChild(*p))
{
AttachedAsLChild(g,p->rc);
AttachedAsLChild(p,v->rc);
AttachedAsRChild(v,p);
AttachedAsRChild(p,g);
}
else
{
AttachedAsRChild(g,v->lc);
AttachedAsLChild(p,v->rc);
AttachedAsLChild(v,g);
AttachedAsRChidl(v,p);
}
}
else
{
if(IsLChild(*p))
{
AttachedAsRChild(p,v->lc);
AttachedAsLChild(g,v->rc);
AttachedAsLChild(v,p);
AttachedAsRChild(v,g);
}
else
{
AttachedAsRChild(g,p->lc);
AttachedAsRChild(p,v->lc);
AttachedAsLChild(v,p);
AttachedAsLChild(p,g);
}
}
if(!gg)
{
(g==gg->lc)?AttachedAsLChild(gg,v):AttachedAsRChild(gg,v);
}
updateHeight(g);updateHeight(p);updateHeight(v);
}
if(p=v->parent)
{
if(IsLChild(*v)
{
AttachedAsLChild(p,v->rc);
AttachedAsRChild(v,p);
}
else
{
AttachedAsRChild(p,v->lc);
AttachedAsLChild(v,p);
}
}
v->parent=NULL;
return v;
(2)Search函数
调用标准BST的内部接口定位目标节点,然后将该节点伸展至根,返回该节点。
template<typename T>BinNodePosi(T)& Splay<T>::Search(const T& e)
{
BinNodePosi(T)p=searchIn(_root,e,_hot);
_root=splay(p?p:_hot);
return _root;
}
(3)Insert函数
Splay::Search()会搜索插入的节点,节点不存在时,该函数会返回_hot,因此可在树根处直接完成新节点的引入。
template<typename T>
BinNodePosi(T)& Splay<T>::Insert(const T& e)
{
BinNodePosi(T) p=search(e);
if(p)return p;
BinNode<T>newRoot(e,NULL);
BinNodePosi(T)Lc=p->lc;
BinNodePosi(T)Rc=p->rc;
if(p->data<e->data)
{
AttachedAsLChild(newRoot,p);
AttachedAsRChild(newRoot,Rc);
}
else
{
AttachedAsLChild(newNode,Lc);
AttachedAsRChild(newNode,p);
}
}
(4)Remove函数
Splay::Search()会把要删除的节点伸展到根,因此直接在删除根节点就可以,然后可在左子树中找一个中序最大的节点,或在右子树中找一个中序最小的节点,重新连接两棵子树即可。