一、红黑树简介
咱先说说红黑树是个啥。红黑树其实就是一种特殊的二叉搜索树，它在普通二叉搜索树的基础上，多了一些规则来保证树的平衡性。想象一下，普通的二叉搜索树就像一个高低不平的山坡，查找数据的时候可能要跑很远；而红黑树呢，就像是把这个山坡修整得比较平缓，查找数据的时候就快多啦。
二、红黑树的5条核心性质详解
1. 每个节点要么是红色，要么是黑色
这就好比给树上的每个节点都涂上了颜色，不是红就是黑。就像给小朋友们分衣服，要么穿红色衣服，要么穿黑色衣服。
2. 根节点是黑色
根节点就像是树的老大，它必须是黑色的。这就好比一个团队的首领，得有个沉稳的形象，黑色就代表着这种沉稳。
3. 每个叶子节点（NIL节点，空节点）是黑色
叶子节点就像是树的末端，它们也得是黑色的。可以把叶子节点想象成队伍末尾的人，也得遵守统一的规则。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的
这就像是一种“颜色搭配”规则。红色节点不能连着红色节点，就像穿红色衣服的小朋友不能挨着穿红色衣服的小朋友，中间得隔个穿黑色衣服的。
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
这意味着从任何一个节点出发，到它下面的叶子节点，经过的黑色节点数量是一样的。就好比从一个地方到另一个地方，不管走哪条路，遇到的黑色标记数量是固定的。
举个例子，假如有这样一棵红黑树：
// Java 示例
class TreeNode {
int value;
boolean isRed;
TreeNode left;
TreeNode right;
public TreeNode(int value, boolean isRed) {
this.value = value;
this.isRed = isRed;
this.left = null;
this.right = null;
}
}
public class RedBlackTreeExample {
public static void main(String[] args) {
// 创建根节点，黑色
TreeNode root = new TreeNode(10, false);
// 创建左子节点，红色
TreeNode leftChild = new TreeNode(5, true);
root.left = leftChild;
// 创建右子节点，红色
TreeNode rightChild = new TreeNode(15, true);
root.right = rightChild;
// 左子节点的左子节点，黑色
TreeNode leftLeftChild = new TreeNode(3, false);
leftChild.left = leftLeftChild;
// 左子节点的右子节点，黑色
TreeNode leftRightChild = new TreeNode(7, false);
leftChild.right = leftRightChild;
// 右子节点的左子节点，黑色
TreeNode rightLeftChild = new TreeNode(12, false);
rightChild.left = rightLeftChild;
// 右子节点的右子节点，黑色
TreeNode rightRightChild = new TreeNode(18, false);
rightChild.right = rightRightChild;
// 这里可以添加更多的检查逻辑来验证红黑树的性质
}
}
在这个例子中，根节点是黑色，红色节点的子节点都是黑色，从每个节点到叶子节点的黑色节点数量都是一样的，符合红黑树的性质。
三、红黑树插入操作的变色与旋转
插入操作基本步骤
当我们要往红黑树里插入一个新节点的时候，默认这个新节点是红色的。为啥呢？因为如果插入黑色节点，很容易就破坏了“从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点”这个性质。
变色与旋转情况分析
情况1：插入节点的父节点是黑色
这种情况最简单，插入红色节点后，红黑树的性质没有被破坏，不需要进行变色和旋转操作。
情况2：插入节点的父节点是红色
这时候就比较麻烦了，因为红色节点不能连着红色节点，所以需要进行变色和旋转操作来调整。
- 变色：把父节点和叔叔节点（父节点的兄弟节点）变成黑色，把祖父节点变成红色。
- 旋转：根据插入节点、父节点和祖父节点的位置关系，可能需要进行左旋或右旋操作。
举个例子，假如我们要往上面的红黑树里插入一个值为4的节点：
// Java 示例
class TreeNode {
int value;
boolean isRed;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int value, boolean isRed) {
this.value = value;
this.isRed = isRed;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class RedBlackTreeInsertExample {
public static void insert(TreeNode root, int value) {
TreeNode newNode = new TreeNode(value, true);
TreeNode current = root;
TreeNode parent = null;
// 找到插入位置
while (current != null) {
parent = current;
if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
newNode.parent = parent;
if (parent == null) {
root = newNode;
} else if (value < parent.value) {
parent.left = newNode;
} else {
parent.right = newNode;
}
// 调整红黑树
fixInsert(newNode);
}
public static void fixInsert(TreeNode node) {
while (node.parent != null && node.parent.isRed) {
if (node.parent == node.parent.parent.left) {
TreeNode uncle = node.parent.parent.right;
if (uncle != null && uncle.isRed) {
// 情况2.1：叔叔节点是红色
node.parent.isRed = false;
uncle.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
// 情况2.2.1：插入节点是父节点的右子节点
node = node.parent;
leftRotate(node);
}
// 情况2.2.2：插入节点是父节点的左子节点
node.parent.isRed = false;
node.parent.parent.isRed = true;
rightRotate(node.parent.parent);
}
} else {
TreeNode uncle = node.parent.parent.left;
if (uncle != null && uncle.isRed) {
// 情况2.1：叔叔节点是红色
node.parent.isRed = false;
uncle.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
// 情况2.2.1：插入节点是父节点的左子节点
node = node.parent;
rightRotate(node);
}
// 情况2.2.2：插入节点是父节点的右子节点
node.parent.isRed = false;
node.parent.parent.isRed = true;
leftRotate(node.parent.parent);
}
}
}
// 根节点始终为黑色
root.isRed = false;
}
public static void leftRotate(TreeNode node) {
TreeNode rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
public static void rightRotate(TreeNode node) {
TreeNode leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(10, false);
insert(root, 5);
insert(root, 15);
insert(root, 3);
insert(root, 7);
insert(root, 12);
insert(root, 18);
insert(root, 4);
}
}
在这个例子中，插入值为4的节点后，根据红黑树的规则进行了变色和旋转操作，保证了红黑树的性质。
四、红黑树删除操作的变色与旋转
删除操作基本步骤
删除节点的时候，要先找到要删除的节点，然后根据节点的情况进行处理。如果要删除的节点有两个子节点，需要找到它的后继节点（右子树中最小的节点）来替换它；如果要删除的节点只有一个子节点或者没有子节点，直接删除就可以了。
变色与旋转情况分析
当删除一个黑色节点的时候，可能会破坏红黑树的性质，需要进行变色和旋转操作来调整。
- 变色：把相关节点的颜色进行调整，保证红黑树的性质。
- 旋转：根据节点的位置关系，进行左旋或右旋操作。
举个例子，假如我们要删除上面红黑树中值为5的节点：
// Java 示例
class TreeNode {
int value;
boolean isRed;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int value, boolean isRed) {
this.value = value;
this.isRed = isRed;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class RedBlackTreeDeleteExample {
public static TreeNode delete(TreeNode root, int value) {
TreeNode nodeToDelete = findNode(root, value);
if (nodeToDelete == null) {
return root;
}
TreeNode y = nodeToDelete;
boolean yOriginalColor = y.isRed;
TreeNode x;
if (nodeToDelete.left == null) {
x = nodeToDelete.right;
transplant(root, nodeToDelete, nodeToDelete.right);
} else if (nodeToDelete.right == null) {
x = nodeToDelete.left;
transplant(root, nodeToDelete, nodeToDelete.left);
} else {
y = minimum(nodeToDelete.right);
yOriginalColor = y.isRed;
x = y.right;
if (y.parent == nodeToDelete) {
x.parent = y;
} else {
transplant(root, y, y.right);
y.right = nodeToDelete.right;
y.right.parent = y;
}
transplant(root, nodeToDelete, y);
y.left = nodeToDelete.left;
y.left.parent = y;
y.isRed = nodeToDelete.isRed;
}
if (!yOriginalColor) {
fixDelete(root, x);
}
return root;
}
public static TreeNode findNode(TreeNode root, int value) {
TreeNode current = root;
while (current != null) {
if (value == current.value) {
return current;
} else if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return null;
}
public static void transplant(TreeNode root, TreeNode u, TreeNode v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
if (v != null) {
v.parent = u.parent;
}
}
public static TreeNode minimum(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public static void fixDelete(TreeNode root, TreeNode x) {
while (x != root && !x.isRed) {
if (x == x.parent.left) {
TreeNode w = x.parent.right;
if (w.isRed) {
// 情况1：兄弟节点是红色
w.isRed = false;
x.parent.isRed = true;
leftRotate(root, x.parent);
w = x.parent.right;
}
if (!w.left.isRed && !w.right.isRed) {
// 情况2：兄弟节点的两个子节点都是黑色
w.isRed = true;
x = x.parent;
} else {
if (!w.right.isRed) {
// 情况3：兄弟节点的右子节点是黑色
w.left.isRed = false;
w.isRed = true;
rightRotate(root, w);
w = x.parent.right;
}
// 情况4：兄弟节点的右子节点是红色
w.isRed = x.parent.isRed;
x.parent.isRed = false;
w.right.isRed = false;
leftRotate(root, x.parent);
x = root;
}
} else {
TreeNode w = x.parent.left;
if (w.isRed) {
// 情况1：兄弟节点是红色
w.isRed = false;
x.parent.isRed = true;
rightRotate(root, x.parent);
w = x.parent.left;
}
if (!w.right.isRed && !w.left.isRed) {
// 情况2：兄弟节点的两个子节点都是黑色
w.isRed = true;
x = x.parent;
} else {
if (!w.left.isRed) {
// 情况3：兄弟节点的左子节点是黑色
w.right.isRed = false;
w.isRed = true;
leftRotate(root, w);
w = x.parent.left;
}
// 情况4：兄弟节点的左子节点是红色
w.isRed = x.parent.isRed;
x.parent.isRed = false;
w.left.isRed = false;
rightRotate(root, x.parent);
x = root;
}
}
}
x.isRed = false;
}
public static void leftRotate(TreeNode root, TreeNode node) {
TreeNode rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
public static void rightRotate(TreeNode root, TreeNode node) {
TreeNode leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(10, false);
insert(root, 5);
insert(root, 15);
insert(root, 3);
insert(root, 7);
insert(root, 12);
insert(root, 18);
insert(root, 4);
root = delete(root, 5);
}
}
在这个例子中，删除值为5的节点后，根据红黑树的规则进行了变色和旋转操作，保证了红黑树的性质。
五、红黑树的应用场景
红黑树在很多地方都有应用，比如：
- 文件系统：在文件系统中，红黑树可以用来管理文件的索引，提高文件查找的效率。
- 数据库：数据库中的索引结构很多都使用红黑树，这样可以快速查找数据。
- 编程语言的标准库：像Java的TreeMap和TreeSet，C++的std::map和std::set，都是基于红黑树实现的。
六、红黑树的技术优缺点
优点
- 高效的查找、插入和删除操作：红黑树的时间复杂度是O(log n)，在处理大量数据的时候，效率比较高。
- 平衡性好：红黑树通过变色和旋转操作，保证了树的平衡性，避免了普通二叉搜索树可能出现的退化问题。
缺点
- 实现复杂：红黑树的插入和删除操作需要进行变色和旋转，实现起来比较复杂，代码量也比较大。
- 空间开销大：每个节点需要额外的颜色信息，会增加一定的空间开销。
七、注意事项
- 插入和删除操作的调整：在进行插入和删除操作的时候，一定要按照红黑树的规则进行变色和旋转，否则会破坏红黑树的性质。
- 代码的健壮性：由于红黑树的实现比较复杂，在编写代码的时候要注意处理各种边界情况，保证代码的健壮性。
八、文章总结
红黑树是一种非常重要的数据结构，它通过5条核心性质保证了树的平衡性，使得查找、插入和删除操作的时间复杂度都是O(log n)。在插入和删除节点的时候，需要根据情况进行变色和旋转操作，来保证红黑树的性质不被破坏。红黑树在文件系统、数据库等领域都有广泛的应用，虽然它的实现比较复杂，但是带来的效率提升是非常显著的。
评论