伸展树

「爱情、让人受尽委屈。」 2023-03-01 13:42 51阅读 0赞

**目录：**

1.  概念
2.  存在的意义
3.  基本的自底向上伸展树：伸展
4.  基本伸展树操作
    
    1.  伸展操作
    2.  查找操作
    3.  插入操作
    4.  删除操作
    5.  合并操作
    6.  启发式合并
    7.  划分操作
    8.  其他操作
5.  优势
6.  缺点
7.  应用（[https://www.cnblogs.com/csushl/p/10122047.html][https_www.cnblogs.com_csushl_p_10122047.html]）
8.  时间复杂度分析
9.  自顶向下的伸展树

### 一.概念 ###

伸展树（Splay Tree），也叫分裂树，是一种[二叉排序树][Link 1]，它能在O(log n)内完成插入、查找和删除操作。它由**丹尼尔·斯立特**Daniel Sleator 和 **罗伯特·恩卓·塔扬**Robert Endre Tarjan 在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。

# #

## 二.存在的意义 ##

**平衡查找树的一些限制：**

1.  平衡查找树每个节点都需要保存额外的信息。
2.  难于实现，因此插入和删除操作复杂度高，且是潜在的错误点。
3.  对于简单的输入，性能并没有什么提高。

**平衡查找树可以考虑提高性能的地方：**

1.  平衡查找树在最差、平均和最坏情况下的时间复杂度在本质上是相同的。
2.  对一个节点的访问，如果第二次访问的时间小于第一次访问，将是非常好的事情。
3.  90-10法则。在实际情况中，90%的访问发生在10%的数据上。
4.  处理好那90%的情况就很好了。

**伸展树（Splay Tree）的来源**

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

### 三.伸展的三种情况 ###

为了在[节点][Link 2]x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：

1.  第一种情况 **zig情况**：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。这和一个普通的单旋转相同。（这种情况是最后一步）  
    ![20200726235954941.png][]
2.  第二种情况 **zig-zag情况**：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。  
    ![20200727000012308.png][]
3.  第三种情况 **zig-zig情况**：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。(注意：将一个循环的步骤都操作完，再继续下一轮循环）  
    ![20200727000026212.png][]

在[节点][Link 2]x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。

例1：旋转节点c到根上  
![20200727000134641.png][]

例2：执行 Splay(1,S)，我们将元素 1 调整到了伸展树 S 的根部。再执行 Splay(2,S)，如图 5 所示，我们从直观上可以看出在经过调整后，伸展树比原来“平衡”了许多。而伸展操作的过程并不复杂，只需要根据情况进行旋转就可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。  
![20200727000228272.png][]

### 四.基本伸展树操作 ###

1.  伸展操作（如上所述）
    
    伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理： 
    
    1.  情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x是y的右孩子，则我们进行一次Zag（左旋）操作。经过旋转，x成为二叉查找树S的根节点，调整结束。即：如果当前结点父结点即为根结点，那么我们只需要进行一次简单旋转即可完成任务，我们称这种旋转为单旋转。
    2.  情况二：节点x的父节点y不是根节点，y的父节点为z，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。即：设当前结点为X，X的父结点为Y，Y的父结点为Z，如果Y和X同为其父亲的左孩子或右孩子，那么我们先旋转Y，再旋转X。我们称这种旋转为一字形旋转。
    3.  情况三：节点x的父节点y不是根节点，y的父节点为z，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操作或者Zag-Zig操作。即：这时我们连续旋转两次X。我们称这种旋转为之字形旋转。
2.  查找操作  
    Find(x,S)：判断元素x是否在伸展树S表示的有序集中。  
    首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。
3.  插入操作
    
    Insert(x,S)：将元素x插入伸展树S表示的有序集中。  
    首先，也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，再执行Splay(x,S)。
4.  删除操作
    
    Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。  
    首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调整到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。  
    ![20200727001830337.png][]
5.  合并操作  
    join(S1,S2)：将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1中最大的一个元素x，再通过Splay(x,S1)将x调整到伸展树S1的根。然后再将S2作为x节点的右子树。这样，就得到了新的伸展树S。
6.  启发式合并  
    当S1和S2元素大小任意时，将规模小的伸展树上的节点一一插入规模大的伸展树，总时间复杂度O(Nlg^2N)。
7.  划分操作  
    Split(x,S)：以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。首先执行Find(x,S)，将元素x调整为伸展树的根节点，则x的左子树就是S1，而右子树为S2。
8.  其他操作  
    除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。  
    通常来说，每进行一种操作后都会进行一次Splay操作，这样可以保证每次操作的平摊时间复杂度是O(logn)。

## ##

### 五.优点 ###

*  可靠的性能——它的平均效率不输于其他[平衡树][Link 3]。
 *  存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。

由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准红黑树没有任何不同，从空间角度来看，它比[Treap][]、[SBT][]、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并，并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当，常数较高。

### 六.缺点 ###

伸展树最显著的缺点是它有可能会变成一条[链][Link 4]。这种情况可能发生在以非降顺序访问n个元素之后。然而[均摊][Link 5]的最坏情况是对数级的——O(log*n*)。

### 七.自顶向下的伸展树 ###

在自底向上的伸展树中，我们需要求一个节点的父节点和祖父节点，因此这种伸展树难以实现。因此，我们可以构建自顶向下的伸展树。  
        当我们沿着树向下搜索某个节点X的时候，我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。没有被移走的节点构成的树称作中树。在伸展操作的过程中：

1.  当前节点X是中树的根。
2.  左树L保存小于X的节点。
3.  右树R保存大于X的节点。 开始时候，X是树T的根，左右树L和R都是空的。

和前面的自下而上相同，自上而下也分三种情况：

1.  **zig：**  
    ![20200727002523127.png][]  
    如上图，在搜索到X的时候，所查找的节点比X小，将Y旋转到中树的树根。旋转之后，X及其右子树被移动到右树上。很显然，右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置，也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点，其值越大。读者可以分析一下树的结构，原因很简单。
2.  **zig-zig:**  
    ![20200727002546413.png][]  
    在这种情况下，所查找的节点在Z的子树中，也就是，所查找的节点比X和Y都小。所以要将X，Y及其右子树都移动到右树中。首先是Y绕X右旋，然后Z绕Y右旋，最后将Z的右子树（此时Z的右子节点为Y）移动到右树中。注意右树中挂载点的位置。
3.  **zig-zag:**  
    ![20200727002609727.png][]  
    在这种情况中，首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着，对Z进行左旋，将Y及其左子树移动到左树上。这样，这种情况就被分成了两个Zig情况。这样，在编程的时候就会简化，但是操作的数目增加（相当于两次Zig情况)。  
    最后，在查找到节点后，将三棵树合并。如图：  
    ![20200727002645303.png][]

将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。       
下面给出伪代码：       
右连接：将当前根及其右子树连接到右树上。左子结点作为新根。       
左连接：将当前根及其左子树连接到左树上。右子结点作为新根。     
T ： 当前的根节点。

1 Function Top-Down-Splay 
     2      Do 
     3           If X 小于 T Then 
     4                If X 等于 T 的左子结点 Then  
     5                  右连接 
     6                ElseIf X 小于 T 的左子结点 Then 
     7                  T的左子节点绕T右旋 
     8                  右连接 
     9                Else X大于 T 的左子结点 Then 
    10                  右连接 
    11                  左连接 
    12                EndIf    
    13           ElseIf X大于 T Then 
    14                IF X 等于 T 的右子结点 Then 
    15                  左连接 
    16                ElseIf X 大于 T 的右子结点 Then 
    17                  T的右子节点绕T左旋 
    18                  左连接 
    19                Else X小于 T 的右子结点‘ Then 
    20                  左连接 
    21                  右连接 
    22                EndIf 
    23           EndIf 
    24      While  ！(找到 X或遇到空节点) 
    25       组合左中右树 
    26 EndFunction

同样，上面的三种情况也可以简化：

1   Function Top-Down-Splay
     2         Do 
     3               If X 小于 T Then 
     4                    If X 小于 T 的左孩子 Then 
     5                      T的左子节点绕T右旋 
     6                    EndIf    
     7                 右连接 
     8               Else If X大于 T Then 
     9                    If X 大于 T 的右孩子 Then 
    10                      T的右子节点绕T左旋
    11                    EndIf 
    12 左连接 
    13          EndIf 
    14 While  !(找到 X或遇到空节点) 
    15 组合左中右树 
    16     EndFuntion

下面是一个查找节点19的例子：       
在例子中，树中并没有节点19,最后，距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点，但是节点20没有成为新根，这和节点20在原来树中的位置有关系。

![20200727003009271.png][]

这个例子是查找节点c：

![20200727003030532.png][]

[https_www.cnblogs.com_csushl_p_10122047.html]: https://www.cnblogs.com/csushl/p/10122047.html
[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/10905079
[Link 2]: https://baike.baidu.com/item/%E8%8A%82%E7%82%B9
[20200726235954941.png]: /images/20230208/1a9576e3aca8435b9b92ffbdaa46d949.png
[20200727000012308.png]: https://img-blog.csdnimg.cn/20200727000012308.png
[20200727000026212.png]: https://img-blog.csdnimg.cn/20200727000026212.png
[20200727000134641.png]: https://img-blog.csdnimg.cn/20200727000134641.png
[20200727000228272.png]: https://img-blog.csdnimg.cn/20200727000228272.png
[20200727001830337.png]: https://img-blog.csdnimg.cn/20200727001830337.png
[Link 3]: https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E6%A0%91
[Treap]: https://baike.baidu.com/item/Treap
[SBT]: https://baike.baidu.com/item/SBT
[Link 4]: https://baike.baidu.com/item/%E9%93%BE
[Link 5]: https://baike.baidu.com/item/%E5%9D%87%E6%91%8A
[20200727002523127.png]: https://img-blog.csdnimg.cn/20200727002523127.png
[20200727002546413.png]: https://img-blog.csdnimg.cn/20200727002546413.png
[20200727002609727.png]: https://img-blog.csdnimg.cn/20200727002609727.png
[20200727002645303.png]: https://img-blog.csdnimg.cn/20200727002645303.png
[20200727003009271.png]: https://img-blog.csdnimg.cn/20200727003009271.png
[20200727003030532.png]: https://img-blog.csdnimg.cn/20200727003030532.png