伸展树的实现与分析：伸展算法的实现，查找、插入、删除算法的实现 (C++)

短命女 2022-05-17 12:44 143阅读 0赞

## 伸展树(splay tree) ##

通常在任意数据结构的生命期内,不仅执行不同操作的概率往往极不均衡,而且各操作之间具有极强的相关性,并在整体上多呈现出极强的规律性。其中最为典型的,就是所谓的“数据局部性”(data locality),这包括两个方面的含义:

**1)刚刚被访问过的节点,极有可能在不久之后再次被访问到  
2)将被访问的下一节点,极有可能就处于不久之前被访问过的某个节点的附近**

因此,只需将刚被访问的节点,及时地“转移”至树根(附近),即可加速后续的操作。“**即用即前移**”的启发式策略,将最为常用的数据项集中于列表的前端,从而使得单次操作的时间成本大大降低。

1.逐层扩展

每访问过一个节点之后,随即反复地以它的父节点为轴,经适当的旋转将其提升一层,直至最终成为树根。

![70][]

随着节点E的逐层上升,两侧子树的结构也不断地调整,故这一过程也称作**伸展(splaying)**,而采用这一调整策略的二叉搜索树也因此得名。

目前的策略仍存在致命的缺陷对于很多访问序列,单次访问的分摊时间复杂度在极端情况下可能高达O(n)。

2.双层伸展

为克服上述伸展调整策略的缺陷,一种简便且有效的方法就是:将逐层伸展改为双层伸展。具体地,每次都从当前节点v向上追溯两层(而不是仅一层),并根据其父亲p以及祖父g的相对位置,进行相应的旋转。以下分三类情况,分别介绍具体的处理方法。

\* **zig-zig/zag-zag**

![70 1][]

如此连续的两次zig旋转,合称**zig-zig调整**。另一种完全对称的情形——通过连续的两次逆时针旋转实现调整,合称**zag-zag操作**。

\* **zig-zag/zag-zig**

![70 2][]

如此zig旋转再加zag旋转,合称**zig-zag调整**。另一完全对称的情形——通过zag旋转再加zig旋转实现调整,合称**zag-zig操作**。

\* **zig/zag**

![70 3][]

只需围绕p = r做顺时针旋转zig(p),即可如图(b)所示,使v最终攀升至树根,从而结束整个伸展调整的过程。

zag调整与之对称。

3.伸展树的实现

伸展树接口定义

基于BST类,可定义伸展树模板类Splay

#include "../BST/BST.h"     //基于BST实现Splay
    template <typename T> class Splay : public BST<T> { //由BST派生的Splay树模板类
    protected:
        BinNodePosi(T) splay(BinNodePosi(T) v); //将节点v伸展至根
    public:
        BinNodePosi(T) & search(const T& e);    //查找
        BinNodePosi(T) insert(const T& e);    //插入
        bool remove(const T& e);        //删除
    };

与一般的二叉搜索树不同,伸展树的查找也会引起整树的结构调整,故search()操作也需重写。

### 伸展算法的实现 ###

template <typename NodePosi> inline //在节点*p与*lc(可能为空)之间建立父(左)子关系
    void attachAsLChild(NodePosi p, NodePosi lc) { p->lChild = lc; if (lc) lc->parent = p; }
    
    template <typename NodePosi> inline //在节点*p与*rc(可能为空)之间建立父(右)子关系
    void attachAsRChild(NodePosi p, NodePosi rc) { p->rChild = rc; if (rc) rc->parent = p; }
    
    template <typename T> //Splay树伸展算法:从节点v出发逐层伸展
    BinNodePosi(T) Splay<T>::splay(BinNodePosi(T) v) { //v为因最近访问而需伸展的节点位置
        if (!v) return NULL;
        BinNodePosi(T) p; BinNodePosi(T) g; //*v的父亲与祖父
        while ((p = v->parent) && (g = p->parent)) { //自下而上,反复对*v做双层伸展
            BinNodePosi(T) gg = g->parent; //每轮之后*v都以原曾祖父(great-grand parent)为父
            if (IsLChild(*v))
                if (IsLChild(*p)) { //zig-zig
                    attachAsLChild(g, p->rChild); attachAsLChild(p, v->rChild);
                    attachAsRChild(p, g); attachAsRChild(v, p);
                } else { //zig-zag
                    attachAsLChild(p, v->rChild); attachAsRChild(g, v->lChild);
                    attachAsLChild(v, g); attachAsRChild(v, p);
                }
            else if (IsRChild(*p)) { //zag-zag
                attachAsRChild(g, p->lChild); attachAsRChild(p, v->lChild);
                attachAsLChild(p, g); attachAsLChild(v, p);
            } else { //zag-zig
                attachAsRChild(p, v->lChild); attachAsLChild(g, v->rChild);
                attachAsRChild(v, g); attachAsLChild(v, p);
            }
            if (!gg) v->parent = NULL; //若*v原先的曾祖父*gg不存在,则*v现在应为树根
            else //否则,*gg此后应该以*v作为左或右孩子
                (g == gg->lChild) ? attachAsLChild(gg, v) : attachAsRChild(gg, v);
            updateHeight(g); updateHeight(p); updateHeight(v);
        } //双层伸展结束时,必有g == NULL,但p可能非空
        if (p = v->parent) { //若p果真非空,则额外再做一次单旋
            if (IsLChild(*v)) { attachAsLChild(p, v->rChild); attachAsRChild(v, p); }
            else              { attachAsRChild(p, v->lChild); attachAsLChild(v, p); }  
            updateHeight(p); updateHeight(v);
        }
        v->parent = NULL; return v;
    } //调整之后新树根应为被伸展的节点,故返回该节点的位置以便上层函数更新树根

**代码8.2 伸展树节点的调整**

### 查找算法的实现 ###

在伸展树中查找任一关键码e的过程，可实现如打码：

template <typename T> BinNodePosi(T) & Splay<T>::search(const T& e) {  //在伸展树中查找关键码e
        BinNodePosi(T) p = searchIn(_root, e, _hot = NULL);
        _root = splay((p ? p : _hot)); //将最后一个被访问的节点伸展至根
        return _root;
    } //与其它BST不同,无论查找成功与否,_root都指向最后被访问的节点

### 插入算法的实现 ###

为将节点插至伸展树中,固然可以调用二叉搜索树的标准插入算法BST::insert()，再通过双层伸展,将新插入的节点提升至树根。

以上接口Splay::search()已集成了splay()伸展功能,故查找返回后,树根节点要么等于查找目标(查找成功),要么就是\_hot,而且恰为拟插入节点的直接前驱或直接后继(查找失败)。因此,不妨改用如下方法实现Splay::insert()接口。

![70 4][]

如图8.8所示,为将关键码e插至伸展树T中,首先调用伸展树查找接口Splay::search(e),查找该关键码(图(a))。于是,其中最后被访问的节点t,将通过伸展被提升为树根,其左、右子树分别记作T L 和T R (图(b))。

接下来,根据e与t的大小关系(不妨排除二者相等的情况),以t为界将T分裂为两棵子树。比如,不失一般性地设e大于t。于是,可切断t与其右孩子之间的联系(图(c)),再将以e为关键码的新节点v作为树根,并以t作为其左孩子,以T R 作为其右子树(图(d))。

v小于t的情况与此完全对称。

实现代码：

template <typename T> BinNodePosi(T) Splay<T>::insert(const T& e) { //将关键码e插入伸展树中
        if (!_root) { _size++; return _root = new BinNode<T>(e); } //处理原树为空的退化情冴
        if (e == search(e)->data) return _root; //确认目标节点不存在
        _size++; BinNodePosi(T) t = _root; //创建新节点。以下调整<=7个指针以完成局部重构
        if (_root->data < e) { //插入新根,以t和t->rChild为左、右孩子
            t->parent = _root = new BinNode<T>(e, NULL, t, t->rChild); //2 + 3个
            if (HasRChild(*t)) { t->rChild->parent = _root; t->rChild = NULL; } //<= 2个
        } else { //插入新根,以t->lChild和t为左、右孩子
            t->parent = _root = new BinNode<T>(e, NULL, t->lChild, t); //2 + 3个
            if (HasLChild(*t)) { t->lChild->parent = _root; t->lChild = NULL; } //<= 2个
        }
        updateHeightAbove(t); //更新t及其祖先(实际上叧有_root一个)的高度
        return _root; //新节点必然置于树根,返回之
    } //无论e是否存在于原树中,返回时总有_root->data == e

**代码8.4 伸展树节点的插入**

### 删除算法的实现 ###

为从伸展树中删除节点,固然也可以调用二叉搜索树标准的节点删除算法BST::remove(),再通过双层伸展,将该节点此前的父节点提升至树根。然而,同样鉴于Splay::search()已集成了splay()伸展功能,且在成功返回后,树根节点恰好就是待删除节点。因此,亦不妨改用如下方法实现Splay::remove()接口。

![70 5][]

如图8.9所示,为从伸展树T中删除关键码为e的节点,首先亦调用接口Splay::search(e),查找该关键码,且不妨设命中节点为v(图(a))。于是,v将随即通过伸展被提升为树根,其左、右子树分别记作T L 和T R (图(b))。接下来,将v摘除(图(c))。然后,在T R 中再次查找关键码e。尽管这一查找注定失败,却可以**将T R 中的最小节点m,伸展提升为该子树的根**。

得益于二叉搜索树的顺序性,此时节点m的左子树必然为空;同时,T L 中所有节点都应小于m(图(d))。于是,只需将T L 作为左子树与m相互联接,即可得到一棵完整的二叉搜索树(图(e))。如此不仅删除了v,而且既然新树根m在原树中是v的直接后继,故数据局部性也得到了利用。

实现代码：

template <typename T> bool Splay<T>::remove(const T& e) {  //从伸展树中删除关键码e
        if (!_root || (e != search(e)->data)) return false; //若树空或目标关键码不存在,则无法删除
        BinNodePosi(T) w = _root; //assert: 经search()后节点e已被伸展至树根
        if (!HasLChild(*_root)) { //若无左子树,则直接删除
            _root = _root->rChild; if (_root) _root->parent = NULL;
        } else if (!HasRChild(*_root)) { //若无右子树,也直接删除
            _root = _root->lChild; if (_root) _root->parent = NULL;
        } else { //若左右子树同时存在,则
            BinNodePosi(T) lTree = _root->lChild;
            lTree->parent = NULL; _root->lChild = NULL; //暂时将左子树切除
            _root = _root->rChild; _root->parent = NULL; //叧保留右子树
            search(w->data); //以原树根为目标,做一次(必定失败的)查找
    / assert: 至此,右子树中最小节点必伸展至根,且(因无雷同节点)其左子树必空,于是
            _root->lChild = lTree; lTree->parent = _root; //叧需将原左子树接回原位即可
        }
        release(w->data); release(w); _size--; //释放节点,更新规模
        if (_root) updateHeight(_root); //此后,若树非空,则树根的高度需要更新
        return true; //返回成功标志
    } //若目标节点存在且被删除,返回true;否则返回false

**代码8.5 伸展树节点的删除**

[70]: /images/20220517/d57d299cba7b4bc7a185d5fefa18d18a.png
[70 1]: /images/20220517/a27fc0b220464dfc96b1327b234f3146.png
[70 2]: /images/20220517/06b6f9440b0a47dd9b63585ab1a84c5e.png
[70 3]: /images/20220517/895f1164a8644e09a5b80f89ccaa5055.png
[70 4]: /images/20220517/b3a13f4f750345b7b965f11d0653ee10.png
[70 5]: /images/20220517/a6b59dbcc5964179bf0415021836136a.png