平衡树主要关心的是使树不要倾向一方，理想状况下，叶节点只出现在一两个层次上。因此，新近到达的元素威胁到树的平衡，就要立即在局部重新构造树(AVL方法)或重新创建树(DSW方法)，从而纠正这一问题。然儿，这样的重新构造是否总是必要？二叉查找树用来快速插入、检索和删除元素，重要的是执行这些操作的速度而不是树的形状。通过平衡树可以提高效率，但这不是唯一可用的方法。

还记得数据结构与算法-链表(下)中的自组织链表吗？在二叉树的组织结构中也有类似的自适应树概念。它们都是基于一个观点出发而衍生出来的算法：并非所有的元素使用的频率都相同。

例如，如果树中第10层的一个元素不常用，整个程序的效率将不会因访问这一层而受到太大的影响。然而，如果要经常访问这个元素，该元素位于第10层还是靠近根节点就有很大的区别。因此，自适应树中的策略是沿着树向上移动常用的元素，以此方式对树进行重新构造，从而形成一种"优先树"。

类比自组织链表：

根据前移法和换位法，我们为二叉树提出两种可行的策略

移动到根部

访问过元素P之后，从P节点开始不停的旋转，直到P节点成为新的根节点

单一旋转

访问过元素P之后，将P节点围绕其父节点旋转一次即可，根节点除外

使用单一旋转策略，经常访问的元素最终上移到靠近根的地方，这样，以后访问会比以前的访问更快。更重要的一点，即使所有请求的概率相同时，单一旋转技术平均查找时间也仅仅是

PI*n的开根号，算法复杂度介于O(n)和O(lgn)之间，可以接受。

至于"移动到根部"策略，已经确定访问节点的效率是(2ln2)lgn，这一结果在任何概率分布下都成立(也就是说，该结果与特定请求的概率无关)。

单一旋转策略没有改进的余地，因为它的操作比较简单，仅仅是旋转一次即可。"移动到根部"策略还有改进的余地，因为在移动到根部的过程中涉及到多次旋转。如果我们能在将节点移动到根部的过程中使二叉树的形状尽可能平衡，那么总体来看效率会有很大提升。

"移动到根部"策略的一个修改版本称为"张开"策略，该策略根据子节点、父节点和祖父节点之间的链接关系，成对地使用单一旋转。首先，根据被访问节点R，其父节点Q及祖父节点P之间的关系，分为3种情况：

节点R的父节点是根节点同构配置。R是Q的左节点，Q是P的左节点。或者R是Q的右节点，Q是P的右节点异构配置。R是Q的左节点，Q是P的右节点。或者R是Q的右节点，Q是P的左节点

对于第一种情况，只需要旋转R节点一次即可。

对于异构配置，首先旋转R节点，此时，R成了新的父节点，继续旋转R即可。可以发现，和"移动到根部"策略是一样的。

对于同步配置，首先旋转R的父节点即Q，然后再旋转R节点即可。

可以发现，"移动到根部"策略和"张开"策略的差别只有一点，就是在同构配置时旋转的方式不同。

"张开"策略伪代码如下：

事实证明，"张开"策略非常有效，既能把元素移动到根部，也能使整个树趋于平衡，对下一次访问元素有着积极的影响。通过计算，使用"张开"策略构造二叉树的效率与平衡树的效率相当，等于O(mlgn)，其中m是指节点的m次访问。

"张开'策略既关注元素的访问频率也兼顾到树的平衡。在一些元素比其他元素更常用的环境中，该策略执行的很好。但是，如果靠近根部的元素与最底层元素的访问频率差不多，"张开"策略可能并不是最好的选择。换而言之，我们希望有一种策略重点强调树的平衡也能兼顾到元素的访问频率。这就是"半张开"策略。

"半张开"策略是"张开"策略的一个修改版本，差别只有一点。假设已知被访问节点R，其父节点Q及祖父节点P，对于同构配置，"张开"策略需要执行两次旋转，最终R取代了P的位置。但是，对于"半张开"策略，只执行一次旋转，就是将Q围绕P旋转即可。关键逻辑是R节点之后不再旋转了，Q节点成了新的R节点，判断Q节点以及其父节点、祖父节点属于同构还是异构，决定下一步的操作。

"半张开"策略的优势在于使树更倾向于平衡的同时兼顾到元素的访问频率。

以上讨论的自适应树策略既可以用到普通二叉树也可以用到二叉查找树上，因为旋转的操作不会改变二叉查找树的性质。

综上所述，自适应树是对平衡树很好的替代方式，因为不需要专门维护树的平衡，操作也很简单易懂，对于中等数量的数据非常友好。

自适应树的相关问题已经探讨完毕，更多内容需要在实践中摸索，毕竟，实践出真知。

数据结构与算法-二叉查找树平衡(AVL)