AVL Tree

释义 Definition

AVL 树：一种自平衡二叉搜索树。它通过在插入或删除后进行旋转（rotation）来保持平衡，要求任意节点左右子树的高度差（平衡因子）通常不超过 1，从而保证查找、插入、删除在平均与最坏情况下都能保持较好的效率（常见为 \(O(\log n)\)）。

发音 Pronunciation (IPA)

/e vi l tri/

例句 Examples

We used an AVL tree to keep searches fast.
我们使用 AVL 树来保持查询速度快。

After deleting a node, the AVL tree performed rotations to restore balance and keep the height logarithmic.
删除一个节点后，AVL 树通过旋转恢复平衡，从而把树高保持在对数级别。

词源 Etymology

“AVL” 来自提出该数据结构的两位苏联计算机科学家姓氏首字母：Adelson-Velsky 与 Landis。他们在 1962 年的论文中首次系统提出这种自平衡二叉搜索树，因此得名 AVL tree。

相关词 Related Words

• Balanced Tree
• Binary Search Tree
• Rotation
• Height
• Balance Factor
• Red-Black Tree
• B-Tree

文学与著作中的用例 Literary Works

• **G. M. Adelson-Velsky & E. M. Landis (1962)**：An algorithm for the organization of information（提出 AVL 树的经典论文）
• **Thomas H. Cormen et al.**：Introduction to Algorithms（常简称 CLRS；讨论平衡二叉搜索树思想，相关章节常提及 AVL 树）
• Robert Sedgewick & Kevin Wayne：Algorithms（数据结构章节常包含 AVL 树或与其对比的平衡树）
• Donald E. Knuth：The Art of Computer Programming（排序与查找相关内容中涉及平衡搜索树的理论背景与变体）