Balanced Tree

定义 Definition

平衡树：一种（通常是二叉）搜索树的数据结构，通过保持树的高度“不过分偏斜”，使查找、插入、删除等操作通常能在 O(log n) 时间内完成。常见类型有 AVL 树、红黑树、B 树/ B+ 树 等。（在更广义上，“balanced tree”也可指任何保持高度受控的树结构。）

发音 Pronunciation

/ˈbælənst triː/

例句 Examples

A balanced tree makes searching fast.
平衡树能让查找变得很快。

Because the balanced tree keeps its height small, inserts and deletions remain efficient even as the dataset grows.
由于平衡树能保持较小的高度，即使数据集增长，插入和删除也能保持高效。

词源 Etymology

balanced 来自 balance（平衡、使均衡），源于中古法语 balance，再追溯到拉丁语 bilanx（“两盘的天平”，bi- 表“二”，lanx 表“盘/秤盘”）；tree 源于古英语 trēow（树）。合起来的 balanced tree 属于计算机科学术语，用“平衡”来比喻树形结构不向一侧过度倾斜，从而控制高度。

相关词 Related Words

• AVL Tree
• Red-Black Tree
• B-Tree
• B+ Tree
• Binary Search Tree
• Self-Balancing Tree
• Tree Rotation
• Height
• Logarithmic Time

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）——讨论红黑树等平衡树结构与复杂度分析。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）——涉及搜索树、平衡思想与相关算法。
• Algorithms（Robert Sedgewick & Kevin Wayne）——以工程视角讲解平衡搜索树（如红黑树）及其应用。