红黑树

初识红黑树

基础概念

• 红黑树也是一种自平衡的二叉搜索树（通过颜色调整和旋转操作）

• 以前也叫做【平衡二叉B树】(Symmetric Binary B-tree)

性质

红黑树必须满足以下 5 条性质：

1. 节点是红色(RED)或者黑色(BLACK)

2. 根节点是 BLACK

3. 叶子节点（外部节点，空节点）都是 BLACK

4. RED 节点的子节点都是 BLACK

   • RED 节点的 parent 都是 BLACK
   • 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点

5. 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点（即黑色高度相同）

思考：为何这些规则下，就能保证平衡？