一、红黑树的定义
红黑树是一种自平衡的二叉搜索树，它在插入和删除节点时通过旋转和重新着色等操作来保持树的平衡，从而保证了高效的查找、插入和删除操作，时间复杂度为 O (log n)，其中 n 是树中节点的个数。
二、红黑树的性质
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶节点（NIL 节点，空节点）是黑色。
- 如果一个节点是红色，那么它的两个子节点都是黑色。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
三、红黑树的操作
-
插入操作：
- 插入新节点时，新节点默认被着色为红色。
- 然后通过一系列的旋转和重新着色操作来保持红黑树的性质。
- 如果插入的节点的父节点是红色，可能会违反红黑树的性质，需要进行调整。
-
删除操作：
- 删除节点时，首先找到要删除的节点。
- 如果被删除的节点有两个子节点，需要找到它的后继节点进行替换。
- 然后删除该节点，并通过旋转和重新着色操作来保持红黑树的性质。
四、代码实现
以下是用 Java 语言实现红黑树的简单示例代码：
class RBNode {
int key;
boolean isRed;
RBNode left;
RBNode right;
RBNode parent;
RBNode(int key) {
this.key = key;
// 新插入的节点默认为红色
isRed = true;
left = null;
right = null;
parent = null;
}
}
class RedBlackTree {
private RBNode root;
public RedBlackTree() {
root = null;
}
private RBNode grandparent(RBNode node) {
if (node!= null && node.parent!= null) {
return node.parent.parent;
}
return null;
}
private RBNode uncle(RBNode node) {
RBNode grandparent = grandparent(node);
if (grandparent == null) {
return null;
}
if (node.parent == grandparent.left) {
return grandparent.right;
} else {
return grandparent.left;
}
}
private void rotateLeft(RBNode node) {
RBNode 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;
}
private void rotateRight(RBNode node) {
RBNode 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.left) {
node.parent.left = leftChild;
} else {
node.parent.right = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
private void insertFixup(RBNode node) {
while (node!= root && node.parent.isRed) {
if (node.parent == grandparent(node).left) {
RBNode uncleNode = uncle(node);
if (uncleNode!= null && uncleNode.isRed) {
node.parent.isRed = false;
uncleNode.isRed = false;
grandparent(node).isRed = true;
node = grandparent(node);
} else {
if (node == node.parent.right) {
node = node.parent;
rotateLeft(node);
}
node.parent.isRed = false;
grandparent(node).isRed = true;
rotateRight(grandparent(node));
}
} else {
RBNode uncleNode = uncle(node);
if (uncleNode!= null && uncleNode.isRed) {
node.parent.isRed = false;
uncleNode.isRed = false;
grandparent(node).isRed = true;
node = grandparent(node);
} else {
if (node == node.parent.left) {
node = node.parent;
rotateRight(node);
}
node.parent.isRed = false;
grandparent(node).isRed = true;
rotateLeft(grandparent(node));
}
}
}
root.isRed = false;
}
public void insert(int key) {
RBNode node = new RBNode(key);
if (root == null) {
root = node;
// 根节点为黑色
node.isRed = false;
return;
}
RBNode current = root;
RBNode parent = null;
while (current!= null) {
parent = current;
if (node.key < current.key) {
current = current.left;
} else {
current = current.right;
}
}
node.parent = parent;
if (node.key < parent.key) {
parent.left = node;
} else {
parent.right = node;
}
insertFixup(node);
}
}
public class RedBlackTreeExample {
public static void main(String[] args) {
RedBlackTree rbTree = new RedBlackTree();
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30);
rbTree.insert(40);
rbTree.insert(50);
rbTree.insert(60);
rbTree.insert(70);
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
评论（0）