
红黑树(Red-Black Tree)是一种自平衡的二叉查找树。在
红黑树中,每个节点包含一个颜色属性,可以是红色或黑色。
通过对任何一条从根到叶子的路径上各个节点的颜色进行
约束,红黑树确保没有一条路径会比其他路径长出两倍,因
而是近似平衡的。 红黑树满足以下性质:
1. 每个节点非红即黑。
2. 根节点是黑色的。
3. 所有叶子节点(NIL 节点,树尾端的虚拟节点)都是黑色的。
4. 若一个节点是红色的,则它的子节点都是黑色的(从每个叶子到根的所有路径上不
会有两个连续的红色节点)。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 下面是一个
简化版的 Java 实现红黑树的基础结构和插入操作的代码示例:
// 定义颜色枚举
enum Color {
RED, BLACK
}
// 定义红黑树的节点类
class Node {
int data;
// 节点数据
Color color;
// 节点颜色
Node left, right, parent;
// 左右子节点和父节点
// Node 构造函数
public Node(int data) {
this.data = data;
this.left = null;