展开树是一种gydF4y2Ba二叉搜索树gydF4y2Ba．不像其他的变种gydF4y2BaAVL树gydF4y2Ba,gydF4y2Ba红黑树gydF4y2Ba,或者是gydF4y2Ba替罪羊树gydF4y2Ba在美国，展开树并不总是平衡的。相反，它是经过优化的，以便最近访问过的元素能够快速地再次访问。gydF4y2Ba

这个性质在本质上与a相似gydF4y2Ba堆栈gydF4y2Ba．堆栈具有后进先出(Last-In-First-Out, LIFO)属性，所以最近添加的项是访问最快的项。展开树与此类似，当您添加一个新项目时，它将成为树的根。但他们更进一步。即使只是简单地搜索一个项目，它也会成为树的新根。下面的gif显示了展开树如何按顺序插入元素7、3和9。gydF4y2Ba

展开树插入gydF4y2Ba

因为它是不平衡的gydF4y2Ba二叉搜索树gydF4y2Ba，展开树不能保证gydF4y2Ba最坏的gydF4y2Ba $O (\ log_2 (n))gydF4y2Ba$时间，就像平衡二叉搜索树一样。平衡二叉搜索树的高度是gydF4y2Ba最多gydF4y2Ba $\ log_2 (n)gydF4y2Ba$在哪里gydF4y2Ba $ngydF4y2Ba$为树中的节点数。所以，展开树只能保证gydF4y2Ba $O (\ log_2 (n))gydF4y2Ba$摊销gydF4y2Ba时间。gydF4y2Ba

展开树很像其他的二叉搜索树。它们有节点，每个节点有两个子节点，一个在左边，一个在右边。在树的开始处有一个根节点。但是，主要的区别是根节点是gydF4y2Ba总是gydF4y2Ba最后一个被访问的元素。gydF4y2Ba

如果一个元素被插入到树中，树将被旋转，以使它出现在根位置。同样，如果在树中搜索一个元素，它也会以同样的方式移动。gydF4y2Ba

删除操作在很大程度上取决于实现者。然而，通常情况下，要删除的元素要么与其右子树中最左边的节点交换，要么与其左子树中最右边的节点交换。然后简单地将其从树中删除。gydF4y2Ba

展开树通常用于树间操作，如连接、合并、联合和其他操作gydF4y2Ba集gydF4y2Ba相关的数学运算，因为展开树在这些运算上是有效的。此外，当查询高度偏倚时，使用展开树。也就是说，当一组查询倾向于某个元素时，展开树是有效的。这是因为经常查询的元素会出现在树的顶部。例如，如果使用一棵展开树来存储一组在商店工作的人员的名字，则可能查询最多的是经理的名字。正因为如此，经理的名字大部分时间都被放在树的最顶端，这样就很容易再次找到。gydF4y2Ba

你能想到对集合{1,2,3,4}的插入操作的顺序会使展布树非常低效吗?提示:它将使查找的平均情况gydF4y2Ba $O (n)gydF4y2Ba$就像一个普通的gydF4y2Ba二叉搜索树gydF4y2Ba．gydF4y2Ba

显示答案gydF4y2Ba

如果我们按升序插入集合{1,2,3,4}，树将完全没有分支因子。展开树是这样的。gydF4y2Ba

1 2 3 4 5 6 7gydF4y2Ba

4 / 3 / 2 / 1gydF4y2Ba

如果我们把它们插入，结果也是一样的gydF4y2Ba下行gydF4y2Ba秩序。这棵树就是镜像。gydF4y2Ba

展开树支持所有的典型gydF4y2Ba二叉搜索树gydF4y2Ba操作——搜索、插入和删除。然而，正是展开树的子操作使所有这些操作成为可能。gydF4y2Ba

向外伸展的gydF4y2Ba

八字树就是靠八字树存活的gydF4y2Ba约gydF4y2Ba平衡。要展开一个节点，需要在节点上重复执行展开步骤，直到节点上升到顶部。为了决定要执行什么样的展开步骤，树考虑了三种可能性:gydF4y2Ba

1. 节点的父节点是根节点gydF4y2Ba
2. 节点是右子结点的左子结点(或左子结点的右子结点)gydF4y2Ba
3. 节点是左子结点的左子结点(或右子结点的右子结点)gydF4y2Ba

如果节点的父节点是根节点，我们只需要旋转一次就可以使它成为根节点。如果节点是根节点的左子节点，则执行右旋转，如果节点是根节点的右子节点，则执行左旋转。这和an的旋转完全一样gydF4y2BaAVL树gydF4y2Ba．这种情况有时被称为“zig”情况。gydF4y2Ba

如果节点是右子节点的左子节点，则需要执行两次旋转。设N是我们要展开的节点，P是它的父节点，G是它的祖父节点。它首先向右旋转N和P，然后向左旋转N和G。如果节点是左子节点的右子节点，则执行相反的操作。它首先向左旋转N和P，然后向右旋转N和G。这有时被称为“之字形”情况。gydF4y2Ba

如果节点是左子节点的左子节点，也有两次旋转。首先，G和P向右旋转。然后X和P向右旋转。如果节点是右子节点的右子节点，则先将G和P向左旋转，然后将X和P向左旋转。gydF4y2Ba

这是“之字形”情况的一个例子。圆圈表示树中的节点，它们下面的三角形表示子树。节点9正在被访问。首先，它的父结点7向左旋转。然后节点9和它原来的祖父节点12一起向右旋转。gydF4y2Ba

斜面曲折的旋转gydF4y2Ba

在节点成为根节点之前，将在节点上使用所有这三种情况(“zig”情况将是最后执行的情况)。gydF4y2Ba

搜索gydF4y2Ba

一旦实现了展开，搜索就很简单了。若要搜索节点，请使用gydF4y2Ba二分查找gydF4y2Ba沿着树向下查找节点。然后，在该节点上执行展开，将其带到树的顶部。gydF4y2Ba

插入gydF4y2Ba

要插入一个节点，请使用二叉搜索在树的底部找到它的适当位置。然后在那个节点上执行展开。gydF4y2Ba

删除gydF4y2Ba

删除是唯一一个对实现者有一定回旋余地的操作。毕竟，当您移除一个节点时，没有明显的节点需要展开。gydF4y2Ba

一个典型的实现是，程序员可以用左子树中最右边的节点或右子树中最左边的节点切换要删除的节点。然后可以删除节点，而不会对树产生任何影响(因为它没有子节点)。gydF4y2Ba

另一种方法是先将要删除的节点展开，使其成为根节点。然后删除。我们剩下两个独立的树，然后使用join操作将它们连接在一起，我们将看到这一点gydF4y2Ba晚些时候gydF4y2Ba．gydF4y2Ba

无论如何，一个典型的实现最终将显示被删除节点的父节点。这同样取决于实现者的判断。gydF4y2Ba

除了搜索、插入、删除和有助于这三种操作的展开外，展开树还具有额外的操作。由于展开操作，这些操作在展开树中比在其他树中快得多。这也是展开树对软件如此有吸引力的原因之一。gydF4y2Ba

加入gydF4y2Ba

为了连接两棵树，S和T，使S中的元素小于T中的所有元素，必须有两件事发生。首先，展开S中最大的元素，结果S的根是S中最大的节点，它没有右子节点。第二步，将S的根的右子结点设为t的根，得到的树是agydF4y2Ba二叉搜索树gydF4y2Ba．gydF4y2Ba

分裂gydF4y2Ba

给定一个节点，在该节点上拆分一棵树会得到两棵树。一棵树包含所有小于或等于节点的元素，而另一棵树包含所有大于节点的元素。首先，我们将把节点展开到根节点。然后，我们取根结点的右子结点，使它成为自己的树。现在有两棵树满足分裂条件。gydF4y2Ba

记住，在某些情况下，展形树的效率非常低，最坏的情况下展形树的渐近复杂度是线性时间运算。然而，这经常被忽视，因为gydF4y2Ba平摊分析gydF4y2Ba，所以人们总是认为展开树有gydF4y2Ba $O (\ log_2 (n))gydF4y2Ba$时间的操作。gydF4y2Ba

参见:gydF4y2Ba大O符号gydF4y2Ba．gydF4y2Ba

*平摊gydF4y2Ba

展开树的主要优点是，它将查询最多的节点保留在树的顶部，从而减少后续查询的时间。这种引用的局域性使得展开对于诸如编程语言的垃圾收集或缓存系统等系统非常有用。gydF4y2Ba

展开树也有较低的内存开销，类似于gydF4y2Ba替罪羊树gydF4y2Ba．这使得它们对记忆敏感的程序很有吸引力。gydF4y2Ba

展开式树的最大缺点是它们可能是线性的，就像我们在gydF4y2Ba概念问题gydF4y2Ba．这对性能非常不利，尽管这种情况也非常罕见。gydF4y2Ba