数据结构_平衡二叉搜索树（伸展树 splay tree）

小灰灰 2022-05-21 20:19 192阅读 0赞

## splay tree ##

与之前介绍的[AVL树][AVL]一样，伸展树也是平衡二叉搜索树的一种形式。首先，鉴于数据访问的局部性在实际应用中普遍存在，将按照“最常用者优先”的启发策略，引入并且实现伸展树。尽管最坏的情况下单次操作需要O(n)时间，但其分摊意义仍然在O(log(n))以内。并且相比于AVL树，伸展树无需时刻都严格的保持全树的平衡。

*  局部性  
    数据的局部性：刚刚被访问过的元素，极有可能很快地在此被访问，或者出现在不久访问之前元素的附近。  
    对于BST而言，数据的局部性体现为：刚被访问过的节点，极有可能很快地在此被访问。

--------------------

例：考虑m次连续的查找（m>>n=|BST|）若采用AVL，总共需要O(mlog(n))。此时，如果利用数据的局部性，可以使得更快？这里采用自适应链表举例。  
![这里写图片描述][70]  
当我们访问一个元素时就将其移动到链表的前端去，虽然最开始我们的数据是随机分布的，但是  
在足够长的时间使用之后，经常被访问的元素就会集中到一个区域去（如下图），这个区域的访问效率较高。因此，我们可以在一个足够长的时间跨度之内获得比此前更高的时间效率。  
![这里写图片描述][70 1]  
借助这种想法，来改进BST访问效率：  
![这里写图片描述][70 2]  
此时，该如何实现？

--------------------

**伸展构思**

*  **逐层伸展**  
    直接的方式：每访问过一个节点，随机就将其转移至树根。通过反复地以他的父节点为轴，通过zig或zag旋转将其提升一层（一步一步往上爬）。  
    ![这里写图片描述][70 3]  
    最坏情况：  
    如果按照上述逐层伸展一步一步往上爬，会出现最坏的情况，这里通过一个实例来说明：

--------------------

首先从空树开始依次插入\{0，1，2，3，4\}。如下所示：  
![这里写图片描述][70 4]  
然后通过调用search()接口，从小到大依次访问各个节点。  
![这里写图片描述][70 5]  
![这里写图片描述][70 6]  
有上图可以发现，经过一轮访问循环之后树的形态完全复原。  
![这里写图片描述][70 7]  
一般若节点的总数为n，访问一轮所需要做的旋转次数为：  
(n-1)+\{(n-1)+(n-2)+…..+1\}=(n^2+n-2)/2=O(n^2)  
对此分摊下来，每次访问的平均至少需要O(n)时间。由于访问一轮之后树的形态复原，若访问次数m>>n，则总体需要的时间=O(m\*n)。  
**如何回避这类最坏的访问序列？**  
通过双层伸展改进。

--------------------

*  **双层伸展**  
    为了克服单层伸展的缺陷，**将逐层伸展改为双层伸展。**具体的，每次都从当前节点v向上追溯两层（而不是一层，树高会降低），并根据父亲p以及祖父g的相对位置，进行相应的旋转，分成三种情况：
    
    1、zig-zig/zag-zag（子孙同侧）  
    ![这里写图片描述][70 8]  
    上图中，v是p的左孩子，p是g的左孩子。只需要对应的做两次zig（顺时针）旋转即可。对应的，还有一种完全对称的情况（v是p的右孩子，p是g的右孩子，此时只需要做对应的两次zag（逆时针）旋转即可。）
    
    2、zig-zag/zag-zig（子孙异侧）  
    ![这里写图片描述][70 9]  
    上图中，v是p的左孩子，p是g的右孩子。只需要先做一次zig旋转，再做一次zag旋转即可。对应的还有一种完全对称的情况（v是p的右孩子，p是g的左孩子，此时先做一次zag旋转，再做一次zig旋转。）
    
    3、zig/zag  
    ![这里写图片描述][70 10]  
    若v最初的深度为奇数，则经过若干次双层调整之后，最后一次调整时，v的父亲就是树根了。此时只需要对应的做一次zig或zag旋转就可，每轮调整中，这种情况（至多）只发生一次，出现在最后。

效率分析与性能  
同样对与之前的最坏情况，当我们访问最深的节点时，通过双层伸展不仅同样可以将该结点伸展至树根，而且同时可以使树的高度接近于减半。**就树的形态而言，双层伸展策略可折叠被访问子树的分支，从而避免对长分支的连续访问。这就意味着，即使节点v的深度为O(n)，双层伸展既可以将v推至树根，并且可以将对应的分支按几何级数收缩（含羞草）。如下面实例：**

![这里写图片描述][70 11]  
在经过search(1)之后，树的形态变化为：  
![这里写图片描述][70 12]  
虽然，伸展树不能杜绝最坏的情况发生，但是可以有效控制最坏的情况发生的频度，从而在分摊意义下保证了整体的高效率，单次操作均可以分摊在O(log(n))内完成。

**伸展树的实现**

*  伸展树接口定义  
    伸展树类splay，也同样是由BST类派生而来。

#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()接口也需要重写。此外，还有一个特殊的接口splay()用以控制伸展树的伸展。

*  伸展算法的实现如下：

template <typename NodePosi> inline //在节点*p与*lc（可能为空）之间建立父（左）子关系
     void attachAsLChild ( NodePosi p, NodePosi lc ) { p->lc = lc; if ( lc ) lc->parent = p; }
    
     template <typename NodePosi> inline //在节点*p与*rc（可能为空）之间建立父（右）子关系
     void attachAsRChild ( NodePosi p, NodePosi rc ) { p->rc = 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->rc ); attachAsLChild ( p, v->rc );
                 attachAsRChild ( p, g ); attachAsRChild ( v, p );
              } else { //zig-zag
                 attachAsLChild ( p, v->rc ); attachAsRChild ( g, v->lc );
                 attachAsLChild ( v, g ); attachAsRChild ( v, p );
              }
           else if ( IsRChild ( *p ) ) { //zag-zag
              attachAsRChild ( g, p->lc ); attachAsRChild ( p, v->lc );
              attachAsLChild ( p, g ); attachAsLChild ( v, p );
           } else { //zag-zig
              attachAsRChild ( p, v->lc ); attachAsLChild ( g, v->rc );
              attachAsRChild ( v, g ); attachAsLChild ( v, p );
           }
           if ( !gg ) v->parent = NULL; //若*v原先的曾祖父*gg不存在，则*v现在应为树根
           else //否则，*gg此后应该以*v作为左或右孩子
              ( g == gg->lc ) ? 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->rc ); attachAsRChild ( v, p ); }
           else                   { attachAsRChild ( p, v->lc ); attachAsLChild ( v, p ); }
           updateHeight ( p ); updateHeight ( v );
        }
        v->parent = NULL; return v;
     } //调整之后新树根应为被伸展的节点，故返回该节点的位置以便上层函数更新树根

分析：伸展算法总共分为四种情况即zig-zig、zig-zag、zag-zag、zag-zig。这里以zig-zig为例子说明。如下图：  
![这里写图片描述][70 13]  
我们的双层伸展要进行如上图的转换，这里我们借鉴[AVL树][AVL]中“3+4”重构的方法，即不在乎具体的旋转细节，只在乎结果进行拼接，实现如下：

if ( IsLChild ( *v ) )
              if ( IsLChild ( *p ) ) { //zig-zig
                 attachAsLChild ( g, p->rc ); 
                 attachAsLChild ( p, v->rc );
                 attachAsRChild ( p, g ); 
                 attachAsRChild ( v, p );
              } else { /*zig-zag*/}
    else
        if(IsRChild(*p)){
       /*zag-zag*/}
        else{
       /*zag-zig*/}

*  查找算法  
    在伸展树中查找任一关键码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都指向最后被访问的节点

首先，调用[二叉搜素树][Link 1]的通用算法searchIn()找到关键码e的节点，无论查找成功与否，都将调用splay()算法，这也是伸展树不同于其他BBST的本质区别，伸展树的查找算法不在是动态的，它会改变树的拓扑结构。

*  插入算法的实现  
    直观的方法：首先可以调用在[二叉搜索树][Link 1]中介绍的标准插入算法BST::insert()，然后在通过双层伸展，将新插入的节点提升至树根。但是，在插入之前我们肯定首先调用了search()接口，然而splay::search()已经集成了splay()操作。查找失败之后，\_hot就是根节点，因此可以按照下面实现插入操作：  
    ![这里写图片描述][70 14]  
    1、对v进行查找（尽管会失败）  
    2、将t（查找操作最后访问的节点）伸至树根。  
    3、根据v与t的相对大小，将t分解为TL和TR，于是切断t与其右孩子之间的联系，在以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->rc为左、右孩子
           t->parent = _root = new BinNode<T> ( e, NULL, t, t->rc ); //2 + 3个
           if ( HasRChild ( *t ) ) { t->rc->parent = _root; t->rc = NULL; } //<= 2个
        } else { //插入新根，以t->lc和t为左、右孩子
           t->parent = _root = new BinNode<T> ( e, NULL, t->lc, t ); //2 + 3个
           if ( HasLChild ( *t ) ) { t->lc->parent = _root; t->lc = NULL; } //<= 2个
        }
        updateHeightAbove ( t ); //更新t及其祖先（实际上只有_root一个）的高度
        return _root; //新节点必然置于树根，返回之
     } //无论e是否存在于原树中，返回时总有_root->data == e

*  删除算法的实现  
    直观方法：同样也可以调用二叉搜索树标准的节点删除算法，再通过双层伸展，将该节点此前的父节点提升至树根。  
    但是，与插入操作一样，这种方法同样显的迂回，在实施删除操作之前，同样给要调用splay::searvh()接口，这时由于集成了伸展操作，在search()成功返回之后，数根结点就是待删除的节点。因此，可以如下实现：  
    ![这里写图片描述][70 15]  
    如上图所示，首先查找待删除节点，然后将其提升至树根。将结点v摘除之后，然后在TR中再次查照关键码e，虽然这次操作会失败，但是可以将TR中的最小的节点m伸展提升为该子树的树根，由于二叉搜索树的顺序性，所以此时节点m的左子树必然为空，同时TL中所有节点都小于m，于是进行连接就可以得到一颗完整的二叉搜索树，实现如下：

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->rc; if ( _root ) _root->parent = NULL;
        } else if ( !HasRChild ( *_root ) ) { //若无右子树，也直接删除
           _root = _root->lc; if ( _root ) _root->parent = NULL;
        } else { //若左右子树同时存在，则
           BinNodePosi(T) lTree = _root->lc;
           lTree->parent = NULL; _root->lc = NULL; //暂时将左子树切除
           _root = _root->rc; _root->parent = NULL; //只保留右子树
           search ( w->data ); //以原树根为目标，做一次（必定失败的）查找
     / assert: 至此，右子树中最小节点必伸展至根，且（因无雷同节点）其左子树必空，于是
           _root->lc = lTree; lTree->parent = _root; //只需将原左子树接回原位即可
        }
        release ( w->data ); release ( w ); _size--; //释放节点，更新规模
        if ( _root ) updateHeight ( _root ); //此后，若树非空，则树根的高度需要更新
        return true; //返回成功标志
     } //若目标节点存在且被删除，返回true；否则返回false

**总结**  
优点：  
1、相比于AVL树，伸展树不需要节点高度或平衡因子，实现相对简单，并且它的分摊复杂度O(log(n)),与AVL树相当。  
2、局部性强、缓存命中率极高时，效率甚至可以更高(自适应的O(logk))。  
例如：（我们的数据集有n个，但是我们访问的数据只有k个，并且我们的操作次数有m次，）可以理解为下图：  
![这里写图片描述][70 16]  
由于经常访问数据集位于顶部，分摊下来，每次查找要的时间仅为O(logk)。因此，任何m次查找，都在O(mlogk+nlogn)。（因为，在达到常访问的数据集k集中于顶部时，要经历O(nlogn)时间）。  
缺点：  
不能保证单次最坏的情况出现，伸展树的形状通常不平衡，如下图：  
![这里写图片描述][70 17]  
因此，有可能在某个时刻需要访问一个足够深的节点，虽然之后会将这条路径减半，但是之前一次操作还是付出了时间代价，因此，不能适用于单次效率铭感的场合。

[AVL]: https://blog.csdn.net/xc13212777631/article/details/80760427
[70]: /images/20220522/381668d02e3f4451a4b575141cb0dd54.png
[70 1]: /images/20220522/0b08e671456646759d8ab64e7b16d9c1.png
[70 2]: /images/20220522/a5658bb0871943dab244000b818e380b.png
[70 3]: /images/20220522/9ab37018868a4b25b56c672a22f0ca6b.png
[70 4]: /images/20220522/cf94ec72789a43eebcca3f523c998ead.png
[70 5]: /images/20220522/412a62c3d9604db790f4110582f07315.png
[70 6]: /images/20220522/608ae6320f924deda4bf51f25a648967.png
[70 7]: /images/20220522/4cb2166db8334a1a8614efa229782587.png
[70 8]: /images/20220522/e6f05784e5b54132afdf3740f0d4793a.png
[70 9]: /images/20220522/8729664f11454d5491b232f09b9a9fc5.png
[70 10]: /images/20220522/726a486e304d4a0ead1babdc8e2dcaa8.png
[70 11]: /images/20220522/5d4fcd3f3f494baa80d17c9a5b8e2bdb.png
[70 12]: /images/20220522/fe5c357d58bf4ef2aaecf22a679cdda4.png
[70 13]: /images/20220522/870694cfb8844949b4821b0a996fd836.png
[Link 1]: https://blog.csdn.net/xc13212777631/article/details/80752323
[70 14]: /images/20220522/8803bf5c287b4d15a955f88d2727a26c.png
[70 15]: /images/20220522/8ad7eec957044e208ce69ea6de4671fd.png
[70 16]: /images/20220522/0e2ec623bc424cf8ae50a5a0daa914d5.png
[70 17]: /images/20220522/860f204bae1c42de94ba19adbdeae863.png