欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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树一样

Splay Tree

(2)zig-zig/zag-zag与AVL略有差异

Splay Tree

以前绕着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,因此可在树根处直接完成新节点的引入。

Splay Tree


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()会把要删除的节点伸展到根,因此直接在删除根节点就可以,然后可在左子树中找一个中序最大的节点,或在右子树中找一个中序最小的节点,重新连接两棵子树即可。
Splay Tree

相关标签: Splay BST 伸展树