Tree Rotation

释义 Definition

树旋转：在数据结构中，指对二叉搜索树等树形结构进行局部重排（通常围绕某个结点做左旋或右旋），以在不破坏中序遍历有序性的前提下，调整树的形状，从而改善或维持平衡（常见于 AVL 树、红黑树、伸展树等）。

发音 Pronunciation (IPA)

/triː roʊˈteɪʃən/

例句 Examples

A left tree rotation can reduce the height of a heavy right subtree.
一次左旋可以降低右子树过重时的高度。

After inserting new keys, the red-black tree uses tree rotations to restore its balancing properties.
插入新键之后，红黑树会通过树旋转来恢复其平衡性质。

词源 Etymology

tree 来自古英语 trēow（树、木材）；rotation 来自拉丁语 rotare（使旋转），与 rota（轮子）相关。组合成 tree rotation，字面是“树的旋转”，在计算机科学中引申为“通过旋转操作来调整树结构”的专门术语。

相关词 Related Words

• Avl Tree
• Red-Black Tree
• Binary Search Tree
• Balance
• Rebalancing
• Left Rotation
• Right Rotation
• Splay Tree
• Heap

文献与作品 Literary / Notable Works

• Introduction to Algorithms（CLRS，《算法导论》）：在红黑树章节系统讲解旋转及其在修复性质中的作用。
• Algorithms（Robert Sedgewick & Kevin Wayne，《算法》）：在平衡查找树相关内容中介绍旋转思想与实现。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth，《计算机程序设计艺术》第 3 卷）：涉及平衡树与旋转等相关概念（不同版本与章节表述可能略有差异）。