Splay Tree

定义 Definition

伸展树 / 展开树：一种自调整（self-adjusting）的二叉搜索树。每次访问（查找、插入、删除）某个结点后，会通过一系列旋转操作（伸展 splay）把该结点移动到根，从而让“最近访问过的元素”更容易再次被访问。其摊还时间复杂度通常为 **O(log n)**（单次操作可能较慢，但长期平均表现良好）。

发音 Pronunciation (IPA)

/ˈspleɪ triː/

例句 Examples

A splay tree moves the accessed node to the root.
伸展树会把被访问的结点移动到根结点。

Although a single operation can be costly, splay trees achieve good amortized performance over many operations.
尽管单次操作可能代价较高，但伸展树在大量操作下能获得很好的摊还性能。

词源 Etymology

splay 原义有“展开、向外张开”的意思；在该数据结构里指通过旋转把目标结点“伸展/展开”到树根。tree 指树状结构。合起来 splay tree 直观表达了“把访问结点伸展到根的树”。

相关词 Related Words

• Amortized
• Binary Search Tree
• Rotation
• Self-Adjusting
• Treap
• AVL Tree
• Red-Black Tree

文学与著作中的用例 Literary Works

• Self-Adjusting Binary Search Trees（Sleator & Tarjan, 1985）：提出伸展树并给出摊还分析，是最经典的原始论文。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在数据结构章节中介绍伸展树与摊还分析思想。
• Data Structures and Algorithm Analysis（Mark Allen Weiss）：常以伸展树作为自调整结构与摊还分析的代表案例。