平衡二叉树和红黑树

### 平衡二叉树与红黑树的概念及特点 #### 一、平衡二叉树 (AVL Tree) 平衡二叉树是一种特殊的二叉查找树，其核心特性在于保持树的平衡状态。具体来说，对于每一个节点，它的左右子树高度差的绝对值不会超过1[^2]。这种严格的平衡约束使得平衡二叉树能够在任何情况下都维持较低的高度，从而保证了操作的时间复杂度为 \(O(\log n)\)，其中 \(n\) 是树中的节点数量。 当一棵平衡二叉树失去平衡时，通常会通过旋转操作来恢复平衡。常见的旋转方式有四种：单向右旋、单向左旋、双向先左后右旋以及双向先右后左旋[^3]。 #### 二、红黑树 (Red-Black Tree) 红黑树也是一种自平衡二叉查找树，但它对平衡的要求相对宽松一些。相比于平衡二叉树严格控制左右子树高度差不超过1的规定，红黑树允许更高的不平衡程度，只需满足特定的颜色规则即可： 1. 每个节点要么是红色，要么是黑色。 2. 根节点始终是黑色。 3. 所有的叶子节点（NIL节点）也必须是黑色。 4. 如果一个节点是红色，则它的两个子节点必须是黑色。（即不存在连续的红色节点） 5. 对于任意节点而言，从该节点到其后代叶节点的所有路径上包含相同数目的黑色节点[^1]。 由于这些规则的存在，即使在极端情况下，红黑树的最大深度也不会超过 \(2 \times \log_2(n+1)\)[^1]。因此，在大多数实际应用中，红黑树能够提供接近最优性能的同时还简化了许多复杂的调整逻辑——比如仅需重新着色而非频繁执行代价较高的旋转动作就可以完成部分再平衡工作。 #### 三、两者的主要区别 | **对比维度** | **平衡二叉树(AVL)** | **红黑树(RB)** | |---------------------|---------------------------------------------|--------------------------------------------| | 高度差异限制 | 左右子树高度差不得超过1 | 不强制要求固定高度差, 只要遵循五条性质 | | 插入/删除效率 | 更倾向于维护完全平衡, 导致更多旋转 | 较少依赖旋转, 多利用重染色实现局部修正 | | 实现难度 | 结构简单但因频繁旋转增加编码负担 | 虽然概念稍显抽象却减少了不必要的结构调整 | 综上所述，尽管两种数据结构都能有效解决动态集合上的高效查询需求，但在不同场景下各有优劣取舍之处[^2]. ```python class Node: def __init__(self, key, color='red', parent=None, left=None, right=None): self.key = key self.color = color self.parent = parent self.left = left self.right = right def insert_case1(node): """处理新插入节点作为根的情况""" if node.parent is None: node.color = 'black' ```