伸展树SplayTree：一种自调整二叉排序树

"伸展树(Splay Tree)是一种自调整的二叉排序树，由Daniel Sleator和Robert Tarjan提出。这种数据结构能在O(logn)的时间复杂度内完成插入、查找和删除操作，并且不需要像其他平衡二叉树那样维护额外的平衡信息。伸展树的主要思想是通过旋转操作将频繁访问的节点移动到树根，从而加速后续的查找过程。" 伸展树的创建初衷是为了优化二叉查找树的性能。在一系列查找操作中，如果某些节点被频繁访问，它们应该被移动到靠近树根的位置，以减少平均查找时间。伸展树通过每次查找后的伸展操作（splaying）实现这一目标，即将访问过的节点通过旋转操作提升到树根。 伸展操作包括三种基本旋转：单旋转、双旋转和Z形旋转。这些旋转都是成对进行，目的是在保持二叉查找树性质的同时，减少查找路径上节点的深度。 1. 单旋转：如果当前节点X是其父节点P的唯一子节点（即X是P的左子节点或右子节点），则进行单旋转。若X是左子节点，执行右旋；若X是右子节点，执行左旋。旋转后，X成为新树的根，P成为X的子节点。 2. 双旋转：如果当前节点X和其父节点P都是其祖父节点G的同一侧子节点，先对P和G进行一次旋转，再对X和旋转后的P进行旋转。根据X和P在G的子树中的位置，可能是先左旋后右旋，或者先右旋后左旋。 3. Z形旋转（也称zig-zag或L/R旋转）：当P是G的右子节点而X是P的左子节点，或者P是G的左子节点而X是P的右子节点时，先执行X和P之间的旋转，然后执行新P（即原X）和G之间的旋转。 伸展树的自底向上伸展（bottom-up splay）伪码描述了从叶子节点开始，通过一系列旋转将节点X提升到树根的过程。这个过程涉及了节点X、其父节点P和祖父节点G，通过上述的旋转操作逐步将X移动到树的顶层。 总结来说，伸展树是一种动态适应查询模式的数据结构，通过伸展操作自动调整树的形态，使得频繁访问的节点靠近树根，从而提高查找效率。这种自我调整的能力使其在某些应用场景下优于传统的平衡二叉树。