红黑树(Red-Black Tree)
介绍
红黑树是一种自平衡二叉搜索树,最初被称为"对称二叉B树",后来改名为红黑树。因为在每个节点上都增加了一个表示颜色的属性,可以是红色或黑色。红黑树通过着色规则和特定的重新平衡操作(旋转和重新着色)来保持树的平衡。
红黑树中的几个关键概念:
- 节点(Node):包含数据、左右子节点指针、父节点指针及颜色标记(红/黑)
- 着色规则:每个节点被标记为红色或黑色,以满足特定的平衡条件
- 黑高(Black Height):从任一节点到其后代叶节点的路径上黑色节点的数量
- 旋转(Rotation):与AVL树类似的结构调整操作
- 重新着色(Recoloring):改变节点颜色,配合旋转实现平衡
核心特性
红黑树必须满足以下五个性质:
- 每个节点或是红色,或是黑色
- 根节点必须是黑色
- 所有叶子节点(NIL节点)都是黑色
- 如果一个节点是红色,则其两个子节点都是黑色(不能有连续的红色节点)
- 对于每个节点,从该节点到其所有后代叶子节点的路径上,包含相同数量的黑色节点
...