数据结构中的展开树
播放树定义为自平衡二进制搜索树，具有最近访问的元素可以快速再次访问的额外属性。基本操作（例如插入，查找和删除）由splay树在O（logn）摊销时间内执行。对于许多非随机操作序列，即使未知序列的特定模式，扩展树也比其他搜索树更好地工作。二叉搜索树上的所有常规操作都与一个称为“展开”的基本操作结合在一起。
让我们假设对于每个节点a，我们都存储一个实数键(a)。
在任何二叉搜索树中，任何节点a的左子树包含“键”值小于key(a)值的项目，而节点a的右子树包含“键”值大于key(a)值的项目。
在展开树中，我们首先搜索查询项，例如在通常的二叉搜索树中说a-将查询项与根中的值进行比较，如果小于则在左子树中递归搜索，如果大于则在左子树中递归搜索。正确的子树，如果相等，那么我们就完成了。然后，非正式地讲，我们查看每对不相交的连续祖先fa，例如b=parent(a)和c=parent(b)，并完成某些旋转。这些旋转的结果是，a代替了c。
如果a的祖先数为奇数，则a（它是根的子代）的祖先也必须以单独的方式处理，在终端情况下-我们在a和根之间旋转边。该步骤称为zig步骤。
如果a和b都是其各自父级的左子或右子，那么我们首先旋转b与父c之间的边，然后旋转a与父b之间的边。该步骤称为之字形步骤。
如果a是左（分别是右）孩子，b是右（分别是左）孩子，则我们首先在a和b之间旋转边缘，然后在a和c之间旋转边缘，此步骤称为之字形步骤。