1. 逐层伸展
1. 1 宽松均衡
曾经先容过AVL树，这是一种范例适度均衡的二叉搜刮树。你应该还记得，为此我们须要为此中的每一个节点都界说而且引入一个名为均衡因子的指标，而且要求此中全部节点的均衡因子的数值必须介于-1到+1之间。只管相对于理想均衡而言，这种情势的适度均衡，已经在条件上略有放松，但依然显得有些过于苛刻。假如我们留意到，我们还须要在AVL树的动态调解过程中保持这种特性，这种苛刻就更是显而易见了。
假如比喻作人，AVL树就犹如那种，时时鉴戒到处审慎的范例，那么能否成为那类更为洒脱的人呢？也就是说，我们能否承袭一种更为宽松的准则，同时又从长远，从团体来看，依然不失某种意义的均衡性呢？答案是肯定的，答案就是我们这节的主角——伸展树。
1. 2 局部性
现实上，引入伸展树的最初动机非常的根本和原始。详细来说，也就是试图使用所谓的局部性，那么什么是局部性呢？
所谓局部性是现实的盘算机环境中广泛存在的一种规律或征象。详细来说，也就是刚被访问过的数据极有大概很快的被再次访问到。
在现实的生存中，你应该也有雷同的履历。比如，你有大概在机场上偶遇某位时隔五年以致十年的老朋侪，但在紧接着下来的第二天，你们或允许能又会在另一个场合，比如某个集会上在次谋面。
如许一种征象大概规律在信息处置处罚的过程中是广泛存在屡见不鲜的。比如，我们这里讨论的BST就是一个范例的例子，对于BST来说，这一规律可以详细形貌为：我们每次刚刚访问过的某一个节点都有大概很快的会再次被我们访问到，大概推而广之，我么接下来访问的谁人节点即便不是你刚访问过的谁人节点，也不会离它太远，所谓的虽不中，亦不远矣。
通过此前的学习，我们应该知道：对于AVL树而言，每一次查找所需的时间都是logn，因此恣意的一连m次查找，所须要的累计时间无非就是O(m*logn)，这无可厚非。
那么进一步的，假如我们对数据的访问简直具有上述的局部性，那么我们对数据集的访问服从能否做到更高呢？
1. 3 自顺应调解
不妨来观察一个简朴的实例，也就是范例的线性结构——列表。我们知道在列表结构中全部元素都按照它们之间的逻辑关系，可以分列成一个线性的序列，相邻的元素通过引用建立前驱和后继关系。
我们知道在如许的一个结构中对任何一个元素的访问服从将重要取决于它在这个序列中所具有的秩。
详细来说，秩越小，也就是越靠前的元素，访问的服从越高。秩越大，也就是越靠后的元素，访问的服从越低。
假如对于各元素的访问是完全理想随机的，我们恐怕只得云云，而不能奢望有什么实质的改进。
然而如我们刚才所说的，假如对这个聚集的元素的访问具有局部性，以致有极强的局部性，我们就可以通过简明的战略来实现对整个数据聚集的更高效访问。比如一种行之有效的办法是一旦有某个元素刚刚继续访问，我们就立即将它移动到这个序列的最前端。这种本领背后的战略不难懂白。
由于根据局部性，我们接下来将要访问的元素很大概就是我们刚刚访问的谁人元素，而这个元素就在此前刚刚被送到这个序列的最前端，而对于如许一个最前端的元素而言，我们的访问是唾手可得最为便捷的。
从整个数据结构的生命周期而言，如许一个列表结构，即便最初是完全随机分布的，那么在颠末充足长时间的使用之后，在某一段时间内，被会集访问的那些元素都会不谋而合的会集到这个列表的前端去。我们已经知道，这个地区的访问服从是相应更高的。因此我们就可以在一个充足长的时间跨度之内得到比此前更高的访问服从。
好了，如今我们可以回到我们的二叉查找树，为了便于对比，我们不妨将BST的画法旋转90度，详细来说，也就是将树的顶部和树的底部门别与列表的头部与尾部对应起来。这种对应是有原理的，由于在BST中位于顶部的元素相对于位于其他位置，尤其是底部的元素而言访问服从要高得多。因此假如我们盼望借助局部性对BST的访问服从做进一步的优化，就不妨参照列表的这种本领，将在某一段时间内，常常要访问到的元素，通过某种方式尽大概的移送到更加靠近树根的位置，也就是等效的说，要尽大概的低落他们的深度。
那么如许一种构思是否真正的可行呢？假如可行的话，详细的方法又是怎样的呢？
1. 4 逐层伸展
根据刚才的分析，下一个将被访问的节点很有大概就是刚被访问的节点，因此为了进步下一次访问操纵的服从，一种最直接的办法莫过于将刚被访问的谁人节点直接移送到根节点的位置。因此我们就得到了一个简明的战略。
也就是说，任何一个节点，一旦被访问，我们都应随即将它转移至树根的位置。
为了实现如许一个目的，我们所可以或许借助的本领，依然无非是此前所先容过的等价变更（zig zag）。
详细来说，就是zig和zag变更，假如节点V在当前这一层是左孩子，我们就通过对它的父亲做一次zig旋转，使得二者在高度上相互互换。对称的，假如节点V当前是右孩子，就对它的父节点P做一次zag旋转，同样地，颠末如许的一个调解之后，节点V和它的父亲将在高度上互换位置。
总而言之，无论是颠末一次zig旋转照旧zag旋转，对应的节点V都可以在高度上上升一层。
既然云云，我们不妨反复的使用这一本领，使V的高度逐层上升，知道终极抵达树根。
1. 5 实例
来看详细的实例，这是一棵BST。
假设我们要访问333，那么按照刚才的战略，我们须要在以后通过一系列的zig和zag旋转，将它转移到树根的位置。
我们看看详细的过程
- 从333开始，起首我们留意到它是右孩子，以是要找它的父节点285而且做一个逆时针的zag旋转，如许333就上升了一层。
- 接下来它依然是右孩子，以是我们同样须要找到它的父亲，也就是021，而且对021做一次zag旋转，此时333已经成为一棵左孩子。
- 须要对它现在的父亲，也就是448，做一次顺时针的zig旋转，同样333的高度，因此上升一层。这个过程将继续举行下去，也就是我们进而对新的父亲468做一次相应的顺时针旋转，以及对末了一个父亲641，做一个顺时针的旋转。
可以看到不出不测，333颠末多少次zig和zag旋转的组合，终极抵达了树根。从而使得接下来对它的访问，可以险些只须要常数的时间。假如将节点的如许一种调解过程，连贯的来看，我们就会发现，这个节点逐层上升的过程，是一个左右摇晃，不绝伸展的过程，以是我们也称为这种过程为伸展 splay。
1. 6 一步一步往上爬
概括而言，对某个特定节点的伸展调解过程无非就是，自下而上，渐渐做单选调解。
非常故意思的是，假如借用《蜗牛》那首歌中一句歌词来形容这个过程是再贴切不外的了，在这首歌里，我们会唱到，我要一步一步往上爬，形貌的岂非不正是如许一个过程嘛。
按照刚才所设定的战略，也就是任何节点一经访问，就随即被推送至树根，我们已经可以得到某种意义上的伸展树。
然而不幸的是，只管蜗牛那首歌的旋律和歌词都非常风雅，但是就服从而言，那句一步一步向上爬所暗示的战略，并非是最佳的选择，缘故因由在于它有最坏环境。
1. 7 最坏环境
这棵树有do，re，mi，fa，so，la，si雷同于七个音符所构成的一个逐级上升的音阶。请留意，这棵树当前的外形可以形容为是汉字中的一撇。接下来，不妨假设作为一个周期，我们就按照do，re，mi，fa，so，la，si的序次来访问这个树中的各个节点。
- 起首是do，在对它一次查找访问之后，我们将通过伸展，将它推送至树根。
- 接下来，该轮到re，同样，在对它访问之后，我们也须要通过伸展，将它推送至树根。
- 再接下来，该轮到是mi，同样，在对它举行访问之后，我们也须要通过伸展使之成为新的树根。
- 好，后续的过程雷同，不妨直接来看下一个，以及末了的si。
请留意，颠末如许一轮的访问之后，这棵树的形态，又重新的成为了汉字中的一撇。
刚才那样的访问周期，可以雷同于此的一系列快照来形貌
可以看到，假如这棵树的规模是n的话，那么第一个节点所须要的访问本钱应该大抵为n，第二个节点呢，大抵为n-1，而第三个呢，是n-2，以及n-3，以及n-4，以及终极的1。
概括而言，整个周期中各自访问所对应的盘算本钱是按算术级数厘革的，整个周期的长度为n，因此根据我们在第一章已把握的本领，可以推断出，整个周期内所须要的盘算本钱累计因该是 n 2 n^2 n2量级。假如将这个盘算成天职摊到整个周期内的n次操纵，我们就会发现，每次操纵的分摊本钱居然高达Ω（n）。
这个量不光与AVL树的logn相去甚远，而且反过来不难发现，它已经退化成了最原始的线性序列。比如说，list大概vector的水平，因此，如许一种服从以及在背后决定这一服从的伸展战略，都是不能令我们满意的，然而好消息是标题的根源并不在于伸展自己，而是在于我们没有把它运用好。
那么我们又应该怎样在原有的伸展战略根本上举行改进呢？我们立即就可以看到，从量上讲，这种改进并不大，只须要做一处非常非常玄妙的改进。这就犹如一语道破谁人故事一样，作为一条龙，我们现在的伸展战略现实上已经相称完备，它所缺乏的只是可以或许表现其魂魄的那样一只眼睛，没错，不是一双眼睛，而仅仅是一只。
2. 双层伸展
2.1 双层伸展
为伸展树这条龙点上那只传神之眼的是著名盘算机科学家Tarjan。
他的这一点睛之笔可以概括为不再是逐层的去举行伸展，而是将它改变为两层两层的举行。
详细来说，我们须要反复观察，当前正在伸展的节点V、它的父亲p以及祖父g，而且根据这祖孙三代的相对位置，颠末至多两次旋转，使得V可以或许一次性的上升两层。固然，他们大概的相对位置无非上图四种，也就是zig-zig，zag-zag，以及zig-zag和zag-zig。
2.2 子孙异侧
我们先来看所谓之字形的环境，也就是zig-zag大概是zag-zig。
比如上图（左一）就是一种，详细来说，节点V是左孩子，而他的父亲p却是右孩子。此时，我们的改进战略是：
- 起首围绕着节点p做一次顺时针的旋转，从而得到上图（中心）状态，可以看到，v确实上升了一层。
- 接下来，我们再进而围绕着此前的祖父g做一次逆时针的zag旋转，从而将这一局部子树转化为如许一种拓扑结构（右图）。
可以看到，终极的结果是节点v抵达了此前祖父的高度。因此，整个过程的实质调解结果可以明确为是V上升了两层。
然而颠末过细观察，仔细的你大概会发现，如许一种调解方法并没有什么稀罕之处，由于它与我们此前所先容的AVL树的双旋调解是完全等效的。一个zig再加上一个zag，无论是过程照旧终极的结果。
而且进一步的对比你会发现，如许一个调解过程，现实上与刚才的逐层调解，也没有任何实质的区别。
起首对父节点做旋转，进而对祖父节点举行旋转，岂非这不就是逐层伸展的另一种等效情势嘛，换汤不换药。
假如你可以或许观察到这些征象，那非常好，由于这简直就是毕竟。那条龙已经具有一只眼睛，而真正的差异在于另一只眼。
2.3 子孙同侧
现实上，那另一只神奇的眼睛只有在zig-zig或zag-zag的环境下才会发光。
不妨只思量此中一种，比如zig-zig环境，也就是节点v和他的父亲p都是左孩子的环境。在这里为了便于对比，不妨将这祖孙三代逐层伸展调解结果先画出来，也就是v起首颠末父节点p的一次zig旋转上升一层，进而再通过祖父节点g的一次zig旋转再上升一层。我们已经对此非常熟悉，整个过程平庸无奇。我们刚才也讲过，它会导致最坏环境。
我们再来看看，Tarjan所点出的那只眼睛，大概说他所发起的调解方法。这里关键中的关键是我们须要起首越级，从祖父而不是父节点来开始旋转。
- 详细来说，颠末祖父节点的一次顺时针zig旋转，节点p以及v都会上升一层。
- 接下来，进而对这棵局部子树新的树根也就是p再做一次zig顺时针旋转，从而使得v可以或许继续上升一层，成为这棵局部子树的树根。
将新的这种调解方法的结果与此前的逐层调解方法的结果做一对比，坦诚的讲第一次看到Tarjan为这条龙所点上的这只眼睛的时间，我并没有察觉到它有什么与众差异之处，如今你，大概也是如许，没错，各种的奥妙简直不易察觉。由于从结果来看，二者无非都是将v这个节点提拔了两层而已，然而他们毕竟在局部拓扑结构上照旧有玄妙的差异，更告急的是，这种局部的玄妙差异，将导致全局的差异，而那种差异将是根天性的，颠覆性的。
2.4 点睛之笔
为了切实的感受和了解这只眼睛的神奇之处，我们不妨来看如许一个实例。
依然是汉字中的一撇，只不外为了更好的表现结果，我们这里取了更长的一撇。接下来我们不妨恶意的来访问此中最深的谁人节点，由于如许的话，所斲丧的时间将会最多。
- 那么按照Tarjan发起，此时我们不光要关心节点1的父亲，也就是2，同时也要关注它的祖父，也就是3，我们的第一次旋转，应该在祖父而不是父亲的位置上举行，因此，针对这种环境，我们起首对节点3做一次顺时针的zig。
- 接下来才轮到对原先的父亲也就是2来做一次zig，从而形成如许一种局面。v照旧v，只不外上升了两层。
- 节点v，也就是001，拥有了新的一个父亲和新的一个祖父。
继续接纳Tarjan发起的方法，详细来说，要对新的祖父也就是5做一次zig旋转。
然后再对新的这个父亲4做一次zig旋转。
- 那么接下来继续接纳Tarjan的发起，将会通过怎样的一系列双层调解，终极使目的节点1，伸展到树根呢？一连的看下这个过程。 一次双层调解
又一次双层调解
以及再一次
再一次
以及终极再一次，来看下终极这棵树的全貌。
看到结果了吗？不出不测，节点1被伸展到了树根，然而这只是最根本的一个任务。
我们留意到，作为如许一个调解过程的副产物，整棵树的树高已经有了本质的厘革。
你应该记得，我们此前针对逐层伸展所举的谁人最坏的例子。没错，谁人例子之以是很坏，是由于每次只管它可以或许将目的节点调解到树根，但是整棵树的高度却会不得不按照算数级数，亦步亦趋的小步的厘革。于是呢？使得恶意者每次都可以去试图访问它最深的谁人节点，从而导致累计的平方量级的时间复杂度，以及分摊意义上的线性时间。
而如今呢？我们至少可以看出那种恶意的方法将会失效，由于我们这棵树的形态得到了有效的优化。
详细来说，树的高度大抵缩减为原先的一半，接下来假如我们继续恶意的试图去访问它的新的这个最低点，也就是003，我们就会发现，它会继续的优化调解。来看下，调解的过程以及结果。
可以看到，树的高度在此前的根本上又进而缩减了一半。
2.5 折叠结果
为了更好的看到树高的厘革结果，我们不妨来看一棵更大的伸展树。
这是一棵由31个节点所构成的高度为30的伸展树。 我们继续试图恶意的来访问此中最深的也是访问本钱最高的谁人节点1。请留意在访问这个节点之后，对它举行的双层调解过程。尤其是观察，在每一局部，按照Tarjan所发起的方式举行调解之后，对于这棵树的团体所产生的结果。我们来看一下这棵调解之后伸展树的拓扑结构。
不出我们的料想，全树的高度大抵也缩减了一半。接下来假如我们继续试图恶意的访问此中最深的谁人节点，那么在访问完这个节点之后，将同样的通过一系列的双层伸展，将这个节点推送至树根，而且最告急的一个特性是，这棵树的高度会因此继续缩减一半。
2.6 分摊性能
通过刚才的谁人实例不难发现，Tarjan所发起的这种新方法，具有某种意义上的路径折叠结果。
详细来说，包罗最坏节点在内的任何一个节点，一旦颠末访问，再颠末以后的双层调解之后，这个节点所对应的那条路径长度就会随即折减一半。
我们以致可以说，这种结果具有某种意义上的智能。
既然在一棵BST中，我们非常忌讳很深的节点，那么这种折叠结果，自然就会具有对坏节点的修复作用。这就犹如怕羞草那样，一旦它感受到威胁，就会通过敏捷的紧缩，将自己的缺点匿伏起来。
因此在接纳Tarjan所发起的这种新的战略之后，刚才所举的那种最坏环境，将不至一连的发生。现实上可以严格的证明，按照新的战略，就分摊意义而言，单趟伸展操纵所须要的时间都不会凌驾logn。
也就是说，我们如今不光足以应对此前所涉及的那种最坏环境，而且也不会有任何其他的最坏环境，这是一个最好不外的消息了。
2.7 末了一步
固然从完备性角度来看，尚有一个渺小之处须要增补。也就是假如v的深度是奇数而不是偶数，那么在终极一定会发生一种环境，也就是v只有父亲而没有祖父。此时节点v的父亲就应该是全树的根。
我们说这个标题并不严峻，由于这种环境只大概在整个伸展的过程中出现一次，而且只会出如今末了。假如真出这种环境，我们就可以视详细的形态，也就是v此时毕竟是左孩子照旧右孩子相应的做一次zig大概是zag旋转。
既然这种环境在整个伸展的过程中只会出现一次，因此从渐进的意义而言并不会实质的影响整个调解过程的复杂度。
至此，我们应该可以或许明确Tarjan所发起的这种双层调解的战略不光是完备的而且是行之有效的，那么如许一种双层调解的战略，又当怎样详细实现呢？
3 算法实现
3.1 功能接口
这里再次接纳模板类的情势给出伸展树的接口界说。可以看到，作为BBST的又一变种，它自然可以在我们此前已经筹划并实现的BST类的根本上通过派生直接得到。
详细的与AVL树一样，我们也须要重写此中的insert和remove如许两个动态的操纵接口。而与AVL树差异的是，在这里我们还须要重写search接口。
回首一下，在其他的浩繁变种中，search接口都可以视作是静态的，也就是说，它并不会导致树中节点之间拓扑毗连关系的厘革。然而在伸展树中，正如我们此前已经看到的，这是个例外。即便是查找操纵，也会引起全树的结构厘革，因此，这个接口在这里也须要重写。
然而正如我们立即就要看到的，这个接口对于伸展树而言举足轻重。这个接口内部的实质功能无非是完成伸展，因此在这里我们也筹划并提供了一个掩护范例的splay接口，用以实现这个功能。
3.2 伸展算法
这个居于焦点位置的伸展功能，大抵可以实现如下。
其原理云云前我们所先容的。
- 起首要确定待伸展的节点V，以及它的父节点p和祖父节点g，只要二者同时存在，我们就要实行一次双层调解。
- 详细来说无非是分4种环境分别处置处罚。这4种环境，可以通过嵌套的两重if-else判断来加以辨认。比如，假如我们判断V是左孩子，那我们就知道，应该属于zig范例，那么至于是zig-zig大概是zig-zag，只需在进而查抄父节点是左右孩子。相应我们还可以区分zag-zag和zag-zig。
- 每颠末一次双层伸展，我们都须要将局部的这棵新的子树接入到原树中对应的位置，而且更新相应节点的高度信息。
- 在全部的双层伸展都已完成之后，如我们刚才所言，尚有大概要实行一次单层的调解，直至终极，整个伸展得以完成。而V呢，顺遂的成为了新的树根。因此，我们也须要对这个树根做以标识。
那么这里所分出的4种环境，又当怎样详细的分别应对呢？
3.3 四种环境
我们不妨来看此中的一种，也就是zig-zig的环境。
你应该记得，在这种环境下，v以及p都是左孩子。我们也知道，按照Tarjan的战略，应该就局部这棵子树（上左图）调解为这个样子（上右图）。详细来说，也就是g将成为p的右孩子，而p要成为v的右孩子。
~
请留意，如许的变更依然是一个等价变更，局部的这3个节点，以及他们下属的4棵对应的子树，在中序遍历意义上的序次将保持稳固。将他们沿垂直方向都投影到水平线上，就可以验证这一点。
这里接纳的方法与此前的3+4重构非常雷同，我们不妨忽略详细的旋转过程，而代之以直接拼接的方式。
- 也就是说，我们须要将p的右孩子当作g的左孩子。这个结果可以由这一句 attachAsLChild（g，p->rc）完成。
- 那么下一句attachAsLChild（p，v->rc）呢？它的作用是将v的右孩子，也就是这个X转作p的左孩子。
- 而这一句attachAsRChild（p，g）呢？其结果是将g作为p的右孩子。
- 而末了这句attachAsRChild（v，p）的结果雷同。
类外的3种环境与上述雷同。
3.4 查找算法
再看伸展树的查找接口应当怎样实现，这里给出一种大概的实现方法。
起首与通例的BST一样，也须要调用searchIn这个接口，在以root为根的BST中，查找数值为e的节点。
我们知道，查找大概乐成，也大概不乐成。
- 假如查找乐成，我们就须要随即将掷中的节点p，通过刚刚先容的splay算法伸展至树根，而且将掷中的节点，也就是树根返回。
- 假如是失败的环境呢？固然没有掷中的节点，但是我们知道会有一个搜刮路径的止境_hot，在这里，我们也将这个止境通过splay算法伸展至树根。
以是概括而言，无论是乐成大概失败，我们都会在树根处得到一个相称大概近似的节点，不难懂白这种处置处罚本领的原理正是为了充实使用我们此前所先容的局部性。须要夸大的是，既然在内部须要调用splay算法调解树的拓扑结构，以是对于伸展树而言，search接口将不再是一个静态的操纵。这也是伸展树区别其他同类BBST的最本质特点。
那么伸展树的别的两个动态接口，也就是insert和remove又当怎样实现呢？
3.5 插入算法
先来观察插入算法。
按照直观的头脑，调用BST标准的插入算法，然后再按照伸展树的规则，将新节点伸展至树根的位置。
然而我们发现，这种实现方法在这里显得过于迂回曲折。
由于无论怎样在真正实行插入操纵之前，我们一定已经调用过一次search接口，而我们刚刚也已重写过的search接口，现实上已经集成了一个splay操纵。也就是说，即便查找大概失败，在此之后，根节点也一定是_hot节点。
你应该记得，我们的新节点原来就应该作为_hot的左或右孩子接入树中的，既然_hot已经在根节点处唾手可得，我们为什么还要费尽周折的去做更复杂的操纵呢？沿着这一思绪，我们不妨按照上面这种图给出的流程，来完成伸展树的插入算法。
- 详细来说，起首调用重写之后的search接口，而且不失一样平常性，我们的查找是失败的，而且记失败前终极的节点为t，也就是我们此前所说的_hot。
- 接下来，集成在search接口内部的谁人splay操纵，自然会将这个_hot推送至树根位置，如这个图所示（左二）。
- 接下来，我们不妨从逻辑上，将整棵树在t这个位置上一分为二，比如将 t 与它的右子树分离开。
- 接下来，我们可以引入节点v，而且将t以及它的后代作为V的左子树，而原先从t处分离出来的右子树呢？将作为v的右子树，重新接入这棵树中。
纵观整个过程以及终极的结果，我们不难发现，其结果与通常的插入完全一样。详细来说，不光使得一个新节点得以顺遂插入树中，而且同样使它处于树根的位置，就像它曾经被推奉上去。
3.6 删除算法
再观察节点删除算法
同样的，按照直观的头脑，我们大概会起首按照BST的标准删除算法实行删除，再按照伸展树的约定，将与之领进的节点，比如_hot伸展到树根的位置。同样的，这种方法原来也无可厚非，但是在此时，也依然显得有些迂回。
这背后的缘故因由也是雷同的，由于不失一样平常性，假如在删除操纵之前的search操纵是乐成的，那么在查找之后，待删除的目的节点一定已经被推送到了树根的位置。既然云云，我们为何不随即就在树根的位置附迩来完成如许一次删除操纵呢？详细过程如上图所示。
- 同样的，我们也须要颠末一次查找，对待删除的节点举行定位，而且不失一样平常性，不妨假设乐成。
- 于是在紧随厥后集成在search接口内的伸展操纵之后，这个待删除节点自然也就会被伸展并推送到树根。
- 接下来呢？既然他就是待删除的元素，我不妨将这个节点开释。
于是从逻辑上看这个节点的左右子树就变得相互分离，剩下的任务是，怎样将他们重新归并起来。这里有很多种方法。
- 比如可以在右子树中找到一个最小的节点（假如你一时还想不起怎样才华找到这个节点，那么我的发起是不妨回过头看一看此前所先容的中序遍历算法迭代版）。关于如许一个节点，我们不难发现，只管它是右子树中最小者，相对于左子树来说，它却应该是最大者。
- 因此接下来，只要将原先的左子树作为这个节点的左子树毗连上去，就不光可以完成拓扑结构上的毗连，而且可以或许保持全部元素的中序遍历序次，也就是说我们顺遂的将他们合二为一了。
而如许一个过程的团体结果呢？同样是我们所盼望的，详细来说，所须要的删除的节点确实被删除了 ，而且在此之后，作为树根的节点，是一个与此前谁人节点非常邻近的一个。也就是说，在以后局部性将可以继续得到充实的使用。
3.7 综合评价
末了我们来对伸展树的性能和特点做一个综合的回首。
起首须要再次夸大的是相对此前的AVL树，伸展树显得更为机动和变通，它不须要再记载节点的高度大概均衡因子之类的附加信息，因此从编程实现的角度来看会更为轻便易行。而另一方面，就时间复杂度而言，依然可以确保是在logn的范围内，这也与此前的AVL树相称。
请留意，如许一个复杂度界限并没有任何更多的先决条件，包罗我们最初所先容的局部性条件。
毕竟上，当局部性存在的时间，伸展树的性能还会更高。
不妨思量一种极度的环境，也就是局部性非常强的时间，在这个时间，即便数据集的规模可以或许到达n，在相称长的一段时间之内，我们所访问的数据大概只是此中很少的一部门，比如只有远远小于n的k个，而我们的操纵次数呢？却要远宏大于n。
~
比如你用电脑的过程通常就是如许，只管你的硬盘上所存放的数据文件等等是数以万计以致几百万计，但是在很短时间内，你所常常使用的数据通常只是此中非常低的一个百分比。比如当你在online上苦苦做题的几天之内，你所访问的数据很大概是你的硬盘中屈指可数的那么几个文件，是不是。
~
也就是说，这类环境的特点，可以概括为只管我们所存放的数据非常的多，但是在相称长的时间内，我们所访问的只是此中非常小的一部门，假如我们把这个数据集构造为一棵BST，而且接纳伸展树的战略举行自我调解，那么可想而知的是，颠末一段时间的使用之后，我们最常用的那部门数据都会渐渐的会集到树根的附近，以至于其他部门的数据险些可以忽略掉，他们存在与否，已经不甚告急了，也就是说，我们完全可以以为数据集无非就是一个规模为k而不是n的一棵BBST。
~
如许一棵规模为k的BBST其访问的服从自然就应该靠近于每次是logk而不是logn。因此对于任何一个充足长的操纵序列而言，此中每一次操纵的均派时间复杂度也就大抵是logk，固然在到达这种状态之前，我们大抵要颠末通例的n次操纵，每次操纵的时间复杂度是logn。
~
你使用电脑的履历也应该可以或许验证如许一个规律，岂非不是吗？你的每一台新安装的电脑，不都是在颠末一段时间的应用之后，就会变得非常随手，使得在接下来的充足长的时间之内都可以或许飞速的运转。是的，这是由于通常的操纵体系都充实使用了数据访问的局部性，从而使得缓存的掷中率可以或许到达经大概的高。
固然，只管具有以上诸多长处，我们不得不说，伸展树也并非完美无缺，比如只管它的分摊服从很好，但它依然不可以或许包管杜绝单次最坏环境的出现。
现实上，在此前已经看到伸展树的外形在任何时候通常都是不均衡，以致是极其不均衡。
因此我们完全大概在某一个不幸的时候须要访问一个充足深以致是最深的节点。只管伸展树在以后会随即将这条路径紧缩近一半，但是在此前的这次查找过程中你不得不仍需付出极重的代价。因此在对单次操纵服从非常敏感的场合，伸展树依然是不能实用和胜任的。
这类例子固然不多，但也简直存在，比如在手术室里，控制手术东西的步调断乎不能接纳伸展树这一类的数据结构。
固然也正如我们所看到的伸展树的复杂度分析是一个非常复杂的课题，在这里我们只是以形象的方式通过举例举行了肯定的验证，而严格的证明却要更加复杂。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金 |
发表于 2026-2-27 10:34:38