伸展树是一种自调整的二叉搜索树数据结构，这意味着树的结构会根据被访问或插入的元素动态进行调整。换句话说，树会自动重组，使得频繁访问或插入的元素更靠近根节点。
- 伸展树由 Daniel Dominic Sleator 和 Robert Endre Tarjan 于 1985 年首次提出。它具有简单高效的实现特点，允许以 O(log n) 的均摊时间复杂度执行搜索、插入和删除操作，其中 n 是树中的元素数量。
- 伸展树背后的基本思想是通过执行一系列称为“伸展”的树旋转操作，将最近访问或插入的元素移动到树的根部。伸展是一种重组树的过程，它使最近访问或插入的元素成为新的根节点，并逐渐将其余节点向根部移动。
- 由于伸展树具有自调整特性，减少了频繁访问元素的整体访问时间，因此在实践中非常高效。这使它们成为需要快速动态数据结构的应用程序的理想选择，例如缓存系统、数据压缩和网络路由算法。
- 然而，伸展树的主要缺点是它们不保证平衡的树结构，这可能导致在最坏情况下的性能下降。此外，伸展树不适合需要保证最坏情况性能的应用程序，例如实时系统或安全关键系统。
总的来说，伸展树是一种功能强大且通用的数据结构，为频繁访问或插入的元素提供快速高效的访问。它们被广泛应用于各种应用程序中，并在性能和简洁性之间提供了极佳的平衡。
> 伸展树是一种自平衡二叉搜索树，旨在根据键值高效地访问数据元素。
- 伸展树的关键特征在于，每次访问元素时，该元素都会被移动到树的根部，从而为后续访问创建更平衡的结构。
- 伸展树的特点是使用旋转，旋转是树的局部变换，会改变树的形状但保持元素的顺序。
- 旋转用于将被访问的元素带到树的根部，并在多次访问后如果树变得不平衡时，用于重新平衡树。
伸展树中的操作：
- 插入： 要将新元素插入树中，首先执行常规二叉搜索树插入。然后，应用旋转将新插入的元素带到树的根部。
- 删除： 要从树中删除元素，首先使用二叉搜索树搜索找到它。然后，如果该元素没有子节点，直接将其删除。如果它有一个子节点，将该子节点提升到树中的该位置。如果它有两个子节点，找到该元素的后继（其右子树中的最小元素），将其键与要删除的元素交换，然后删除后继节点。
- 搜索： 要在树中搜索元素，首先执行二叉搜索树搜索。如果找到了该元素，应用旋转将其带到树的根部。如果未找到，则对搜索中访问的最后一个节点应用旋转，该节点将成为新的根。
- 旋转： 伸展树中使用的旋转可以是 Zig 旋转或 Zig-Zig 旋转。Zig 旋转用于将节点带到根部，而 Zig-Zig 旋转用于在对同一子树中的元素进行多次访问后平衡树。
以下是旋转操作的分步说明：
- Zig 旋转： 如果一个节点有右子节点，执行右旋转将其带到根部。如果它有左子节点，执行左旋转。
- Zig-Zig 旋转： 如果一个节点有一个孙子节点，它也是其子节点的右或左子节点，则执行双旋转以平衡树。例如，如果节点有一个右子节点，且右子节点有一个左子节点，则执行右-左旋转。如果节点有一个左子节点，且左子节点有一个右子节点，则执行左-右旋转。
- 注意： 具体的实现细节，包括所使用的确切旋转，可能因伸展树的具体形式而异。
伸展树中的旋转
- Zig 旋转
- Zag 旋转
- Zig – Zig 旋转
- Zag – Zag 旋转
- Zig – Zag 旋转
- Zag – Zig 旋转
1) Zig 旋转：
伸展树中的 Zig 旋转操作方式与 AVL 树旋转中的单次右旋转类似。这种旋转导致节点从当前位置向右移动一个位置。例如，请考虑以下场景：
!imageZig Rotation (Single Rotation)