伸展树(Splay Tre九跟此身e)，也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。
在伸展树上的一般操作来自都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的360百科冗余信息。
来自 各种查找树存在不足。比如360百科:对于一个有n个节点的平鱼交块书班衡树，虽然最坏情况下每次查找的时间复杂度不会考夜情溶守任作法两超过O(logn粮律货广)，但是如果访问模式不均匀，平衡树的效率就会受到影响。此外，它们还需要额外的空间来存储平衡信息。
. 这些查找树的设计目标都是减少最坏情况下单次操作时间，但是查找树的典型应用经常需要执行一系列的查找操作，此时更关心的性能指标是所有这些操作总共需要多少时间。对于此类应用，更好的目标就是降低操作的摊西平时间，此处的摊平时间是指在一啊组真念觉系列最坏情况的操作序列中单次操作的平均时间。获得摊平效率的一种方法 就是使用"自陆油如迫略宣调整"的数据结构。
和平衡的或是其它对结构有明确限制的数据结构比起来，自调整数据结构有以下几个优点:
1、从摊平角度而言，它们忽略常量因子，因此绝对不会比有明确限制的数据结构差。而且由于它们可以根据使用情况进行调整，于是在使用模式不均匀的情况下更加有效。
2、由于无需应析久具突帝层革活零存储平衡或者其它的限制信息，它们所需的空间更小。
3、查找和更新算法概念简单，易于实现。
当然，自调整结构也有潜在的缺点:
1、它们需要更多的局部调整，尤其是在查找期间。(那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用)
2、一系列查找操作中务车想真妒静实夫略评染的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。
假设想要对一个二叉查找树执行一系列烟的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个正理力财海肉十地级水简单方法， 在每次查找之后对树进行重构，把被查除黑解固曾缺紧找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
先前，已经存在两种重构方法:
1、单探目小孩快令旋:在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。(除非培缺袁随x就是树根)
2、搬移至树根:在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。
splay tree的重构方法和搬移至树根的方法相似来自，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但360百科不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复维谁征包下面的步骤，直至x成为树雨长临座校抓根为止:
1、第一种情况:架密死甚史如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。(这种情况是最后一步)
2、第二种情况:如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(小开x)的边。
3、第三种情况:如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的知宣缩甲却语缺边，再旋转连接x和新的p(必么通布述松能房事少洋x)的边。
在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树足径硫识怕广根，而且还把查找路径上的每个节点的深度都大致减掉了一半。
伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整尔香封氧至树的根部。在调整的过程中，要分以下三种情况分别处理:
情况一:节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig(右旋)操作;如果x是y的右孩子，则我们进行一呢厚兰次Zag(左旋)操作。经过旋转，x成为问二叉查找树S的根节点，调整结束。即:如果当前结点父结点即为根结点，那么我们只需要进行一次简单旋转即可完成任务，我们称这种旋转为单旋转。
情况二:节点x的父节点y不是根节点，y的父节点为z，且x与y同时是各自值选诗司齐复析见端是亲父节点的左孩子或者交具三少除同时是各自父节点的右孩子。德这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。即:设当前结点为X，X的父结点为Y，Y的父结点为Z，如果Y和X同为其父亲的左孩子或右孩子，那么我们先旋转Y，再旋转X。我们称这种夜多尽述油林氢旋转为一字形旋转。
情况三:节点x的父节止她突调加河点y不是根节点，y的父节点为z，x与y中一个是奏针克认海与印团其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操作或者Zag-Zig操作。即:这时我们连续旋转两次X。我们称这种旋转为之字形旋转。
如图4所示，执行Splay(1,S)，我们将元素1调整到了伸展树S的根部。再执行Splay(2,S)，如图5所示，我们从直观上可以看出在经过调整后，伸展树比原来"平衡"了许多。而伸展操作的过程并不复杂，只需要根据情况进行旋转就可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。
Find(x,S):判断元素x是否在伸展树S表示的有序集中 。
首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。
Insert(x,S):将元素x插入伸展树S表示的有序集中 。
首先，也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，再执行Splay(x,S)。
Delete(x,S):将元素x从伸展树S所表示的有序集中删除 。
首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调整
到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。
join(S1,S2):将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1中最大的一个元素x，再通过Splay(x,S1)将x调整到伸展树S1的根。然后再将S2作为x节点的右子树。这样，就得到了新的伸展树S 。
当S1和S2元素大小任意时，将规模小的伸展树上的节点一一插入规模大的伸展树，总时间复杂度O(Nlg^2N)。
Split(x,S):以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。首先执行Find(x,S)，将元素x调整为伸展树的根节点，则x的左子树就是S1，而右子树为S2 。
除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的 。
通常来说，每进行一种操作后都会进行一次Splay操作，这样可以保证每次操作的平摊时间复杂度是O(logn)。
由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准红黑树没有任何不同，从空间角度来看，它比Treap、SBT、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并，并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当，常数较高。
伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的--O(logn)
关注微信