之前我们谈论过AVL树，这是一种典型适度平衡的二叉搜索树，成立条件是保持平衡因子在[-1,1]的范围内，这个条件已经是针对理想平衡做出的一个妥协了，但依然显得过于苛刻，因为在很多时候我们需要频繁的做重平衡操作，能不能改进一下，让失衡先积累着，然后等到某个时机，一下子全部解决呢？严谨一点来水就是我们能否秉持一种更为宽松的准则，同时又从长远、整体的角度来看，依然不失某种意义上的平衡性呢？
根据写作套路，那肯定就是点题了。。。对！就是伸展树了，他的出现是因为有人注意到了在信息处理过程中的“局部性”，就是刚被访问过的数据，极有可能很快的被再次访问到，针对特性大做文章，就能切中肯綮了，这也是下面我们要分析的细节。
在二叉搜索树里也时常遇到，主要是两种情况：
每次刚刚访问过的某一个节点有可能很快的会再次被我们访问到
下次访问的节点即便不是刚访问过的那个节点，也不会离得太远
通过此前的学习我们已经知道，对于AVL树而 每一次查找所需的时间都是logn，因此任意的连续m次查找，所需要的累积时间就是mlogn，为了改进，就针对这个局部性来做一做文章吧：先来看一个例子，然后类比推理即可。链表里越靠近表头的节点的查找速度越快，遍历所走的步数少嘛，那么如果数据访问有局部性，我们就——访问一个元素后立即把他移动到最前端。
这样做的逻辑是：根据局部性，接下来将要访问的元素很可能就是刚访问的那个元素，而这个元素就在最前端，头部元素的访问是访问是唾手可得的，走一步就到了。从整个数据结构的生命周期而言，这样一个列表结构即便最初是完全随机分布的，在经过了足够长时间的使用之后，在某一段时间内被集中访问的元素都会集中到这个列表的前端去。我们已经知道这个区域（列表前段部分）的访问效率是相应更高的，那就能有更高的访问效率了。
现在回到二叉树，为了对比就让树横过来。
树的顶部元素访问效率更高，所以我们要参照列表，把经常要访问到的元素尽可能的移送到接近树根的位置，也就是要尽可能的降低他们的深度。
那我们就这么办：某个元素一经访问，就把它移到树根处。具体做法就是把被访问元素不断做旋转操作直到抵达树根，这样的策略被称为“逐层伸展”，是一种朴素的想法，但是不够好，因为在最坏情况下树退化为一条单链，我们来个极端的，每次恶意访问最深的节点，就会变成这样：
先注意一下特征：每层只挂了一个节点，这是弊端所在，后面还会提到。然后经过一轮询问，这个树就复原了。看一下整个过程（竖着看）
我们分析一下这一轮操作的代价：假设树的规模是n，访问第一个最深节点的成本是n，第二个节点是n-1，第三个是n-2，然后是n-3，n-4和最终的1。整个成本按算术级数增长，这就很恐怖了，总体时间O（N^2），分摊到整个周期的n次操作，复杂度omiga（N）居高不下，和AVL树的logn相差甚远，这已经沦落到了线性序列的地步。另外还有一个弊端在于：我们需要为此考虑很多种特殊情况。所以这个策略无法让人满意。