- 数据结构与算法
- DSA - 主页
- DSA - 概述
- DSA - 环境设置
- 数据结构
- DSA - 数据结构基础知识
- DSA - 数据结构和类型
- DSA - 数组数据结构
- 链表
- DSA - 链表基础知识
- DSA - 双向链表
- DSA - 循环链表
- 堆栈和队列
- DSA - 堆栈
- DSA - 表达式解析
- DSA-队列
- 图数据结构
- DSA - 图数据结构
- DSA-深度优先遍历
- DSA-广度优先遍历
- DSA——生成树
- 树数据结构
- DSA - 树数据结构
- DSA - 树遍历
- DSA - 二叉搜索树
- DSA - AVL 树
- DSA - 红黑树
- DSA - B 树
- DSA - B+ 树
- DSA - 八字树
- DSA - 尝试
- DSA-堆
- 递归
- DSA - 递归基础知识
- DSA - 河内塔
- DSA - 斐波那契数列
- DSA 有用资源
- DSA - 问题与解答
- DSA - 快速指南
- DSA - 有用的资源
- DSA - 讨论
数据结构和算法-红黑树
红黑树是平衡二叉搜索树的另一种类型，具有两种颜色的节点：红色和黑色。它是一种自平衡二叉搜索树，利用这些颜色在插入和删除操作期间保持平衡因子。因此，在红黑树运算时，内存使用1位存储来容纳每个节点的颜色信息
在红黑树（也称为 RB 树）中，为节点分配颜色时需要遵循不同的条件。
根节点始终为黑色。
任何两个相邻节点都不能是红色的。
树中的每条路径（从根节点到叶节点）必须具有相同数量的黑色节点。
尽管AVL树比RB树更平衡，但AVL树的平衡算法比RB树更严格，通过RB树可以使多次且更快的插入和删除操作更加高效。
图：RB树
红黑树的基本操作
红黑树上的操作包括通常在二叉搜索树上执行的所有基本操作。RB 树的一些基本操作包括 -
插入
删除
搜索
红黑树的插入操作遵循与二叉搜索树相同的插入算法。元素按照二分搜索属性插入，并且作为补充，节点的颜色编码为红色和黑色，以根据红黑树属性平衡树。
按照下面给出的过程，通过维护二叉搜索树和红黑树属性，将元素插入到红黑树中。
情况 1 - 检查树是否为空；将当前节点作为根节点，如果为空，则将节点着色为黑色。
情况 2 - 但如果树不为空，我们将创建一个新节点并将其着色为红色。这里我们面临两种不同的情况 -
如果新节点的父节点是黑色节点，我们将退出操作，树将保持原样。
如果这个新节点的父节点是红色，并且父节点的兄弟节点的颜色是黑色或者不存在，我们将应用合适的旋转并相应地重新着色。
如果这个新节点的父节点是红色，并且父节点的兄弟节点的颜色是红色，则将父节点、兄弟节点和祖父母节点重新着色为黑色。仅当祖父母不是根节点时才重新着色；如果它是根节点，则仅对父节点和兄弟节点重新着色。
插入示例
让我们为前 7 个整数构建一个 RB 树来详细了解插入操作 -
该树被检查为空，因此添加的第一个节点是根并且颜色为黑色。
现在，树不为空，因此我们创建一个新节点并添加下一个红色整数，
这些节点不违反二叉搜索树和 RB 树的属性，因此我们继续添加另一个节点。
树不是空的；我们创建一个新的红色节点及其下一个整数。但新节点的父节点不是黑色节点，
现在的树违反了二叉搜索树和 RB 树的属性；由于父级的同级为 NULL，我们应用适当的旋转并重新着色节点。
现在 RB Tree 属性已恢复，我们向树中添加另一个节点 -
该树再次违反了 RB 树平衡属性，因此我们检查父级的同级节点颜色（在本例中为红色），因此我们只需重新着色父级和同级节点。
接下来我们插入元素 5，这使得树再次违反 RB 树平衡属性。
由于同级为 NULL，我们应用适当的旋转和重新着色。
现在，我们插入元素 6，但违反了 RB 树属性，需要应用其中一种插入情况 -
父节点的兄弟节点是红色的，因此我们对父节点、父节点的兄弟节点和祖父母节点重新着色，因为祖父母不是根节点。
现在，我们添加最后一个元素 7，但这个新节点的父节点是红色的。
由于父级的兄弟为 NULL，我们应用合适的旋转（RR 旋转）
最终的RB Tree就完成了。
删除
红黑树的删除操作必须恢复二叉搜索树和红黑树的所有属性。按照以下步骤对红黑树执行删除操作 -
首先，我们根据二叉搜索树的性质进行删除。
情况 1 - 如果要删除的节点或节点的父节点是红色的，则将其删除。
情况 2 - 如果节点是双黑，则只需删除双黑（当要删除的节点是黑色叶节点时，就会出现双黑，因为它会添加也被视为黑色节点的 NULL 节点）
情况 3 - 如果双黑的兄弟节点也是黑色节点并且其子节点也是黑色，请按照以下步骤操作 -
去除双黑
将其父节点重新着色为黑色（如果父节点是红色节点，则变为黑色；如果父节点已经是黑色节点，则变为双黑）
将父母的兄弟姐妹重新着色为红色
如果双黑节点仍然存在，我们应用其他情况。
情况 4 - 如果双黑节点的兄弟节点是红色，我们执行以下步骤 -
交换父节点和父节点兄弟节点的颜色。
沿双黑方向旋转父节点
重新应用其他合适的案例。
情况 5 - 如果双黑的兄弟节点是黑色节点，但最接近双黑的兄弟节点的子节点是红色，请按照以下步骤操作 -
交换双黑的兄弟姐妹和有问题的兄弟姐妹的孩子的颜色
兄弟节点的旋转方向与双黑相反（即，如果双黑是右子节点，则应用左旋转，反之亦然）
应用案例 6。
情况 6 - 如果双黑的兄弟节点是黑色节点，但距离双黑较远的兄弟节点的子节点是红色，请按照以下步骤操作 -
交换双黑的父节点和同级节点的颜色
沿双黑方向旋转父级（即，如果双黑是右子级，则应用右旋转，反之亦然）
去除双黑
将红色子节点的颜色更改为黑色。
删除示例
考虑上面构建的相同红黑树，让我们从树中删除一些元素。
从树中删除元素 4、5、3。
要删除元素4，我们首先执行二分查找删除。
执行二分查找删除后，RB Tree 属性不会受到干扰，因此树保持原样。
然后，我们使用二分查找删除来删除元素5
但执行二分查找删除后，RB性质就被违反了，即树中的所有路径不持有相同数量的黑色节点；所以我们交换颜色来平衡树。
然后，我们从获得的树中删除节点 3 -
应用二分查找删除，我们通常删除节点 3，因为它是叶节点。我们得到一个双节点，因为 3 是一个黑色节点。
我们应用案例 3 删除，因为双黑的兄弟节点是黑色的，并且它的子节点也是黑色的。在这里，我们删除双黑，重新着色双黑的父级和同级。
所有所需的节点都将被删除，并且 RB Tree 属性将被保留。
搜索
红黑树的搜索操作遵循与二叉搜索树相同的算法。遍历树，将每个节点与要查找的关键元素进行比较；如果找到，则返回成功的搜索。否则，它会返回不成功的搜索。
完成实施
输出
// C++ program for Red black trees algorithmn
#include <iostream>
using namespace std;
struct Node {
int data;
Node *parent;
Node *left;
Node *right;
int color;
};
typedef Node *NodePtr;
class RedBlackTree {
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent) {
node->data = 0;
node->parent = parent;
node->left = nullptr;
node->right = nullptr;
node->color = 0;
}
// Preorder
void preOrderHelper(NodePtr node) {
if (node != TNULL) {
cout << node->data << " ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}
// Inorder
void inOrderHelper(NodePtr node) {
if (node != TNULL) {
inOrderHelper(node->left);
cout << node->data << " ";
inOrderHelper(node->right);
}
}
// Post order
void postOrderHelper(NodePtr node) {
if (node != TNULL) {
postOrderHelper(node->left);
postOrderHelper(node->right);
cout << node->data << " ";
}
}
NodePtr searchTreeHelper(NodePtr node, int key) {
if (node == TNULL || key == node->data) {
return node;
}
if (key < node->data) {
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
// For balancing the tree after deletion
void deleteFix(NodePtr x) {
NodePtr s;
while (x != root && x->color == 0) {
if (x == x->parent->left) {
s = x->parent->right;
if (s->color == 1) {
s->color = 0;
x->parent->color = 1;
leftRotate(x->parent);
s = x->parent->right;
}
if (s->left->color == 0 && s->right->color == 0) {
s->color = 1;
x = x->parent;
} else {
if (s->right->color == 0) {
s->left->color = 0;
s->color = 1;
rightRotate(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = 0;
s->right->color = 0;
leftRotate(x->parent);
x = root;
}
} else {
s = x->parent->left;
if (s->color == 1) {
s->color = 0;
x->parent->color = 1;
rightRotate(x->parent);
s = x->parent->left;
}
if (s->right->color == 0 && s->right->color == 0) {
s->color = 1;
x = x->parent;
} else {
if (s->left->color == 0) {
s->right->color = 0;
s->color = 1;
leftRotate(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = 0;
s->left->color = 0;
rightRotate(x->parent);
x = root;
}
}
}
x->color = 0;
}
void rbTransplant(NodePtr u, NodePtr v) {
if (u->parent == nullptr) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}
void deleteNodeHelper(NodePtr node, int key) {
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL) {
if (node->data == key) {
z = node;
}
if (node->data <= key) {
node = node->right;
} else {
node = node->left;
}
}
if (z == TNULL) {
cout << "Key not found in the tree" << endl;
return;
}
y = z;
int y_original_color = y->color;
if (z->left == TNULL) {
x = z->right;
rbTransplant(z, z->right);
} else if (z->right == TNULL) {
x = z->left;
rbTransplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
rbTransplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
rbTransplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
delete z;
if (y_original_color == 0) {
deleteFix(x);
}
}
// For balancing the tree after insertion
void insertFix(NodePtr k) {
NodePtr u;
while (k->parent->color == 1) {
if (k->parent == k->parent->parent->right) {
u = k->parent->parent->left;
if (u->color == 1) {
u->color = 0;
k->parent->color = 0;
k->parent->parent->color = 1;
k = k->parent->parent;
} else {
if (k == k->parent->left) {
k = k->parent;
rightRotate(k);
}
k->parent->color = 0;
k->parent->parent->color = 1;
leftRotate(k->parent->parent);
}
} else {
u = k->parent->parent->right;
if (u->color == 1) {
u->color = 0;
k->parent->color = 0;
k->parent->parent->color = 1;
k = k->parent->parent;
} else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = 0;
k->parent->parent->color = 1;
rightRotate(k->parent->parent);
}
}
if (k == root) {
break;
}
}
root->color = 0;
}
void printHelper(NodePtr root, string indent, bool last) {
if (root != TNULL) {
cout << indent;
if (last) {
cout << "R----";
indent += " ";
} else {
cout << "L----";
indent += "| ";
}
string sColor = root->color ? "RED" : "BLACK";
cout << root->data << "(" << sColor << ")" << endl;
printHelper(root->left, indent, false);
printHelper(root->right, indent, true);
}
}
public:
RedBlackTree() {
TNULL = new Node;
TNULL->color = 0;
TNULL->left = nullptr;
TNULL->right = nullptr;
root = TNULL;
}
void preorder() {
preOrderHelper(this->root);
}
void inorder() {
inOrderHelper(this->root);
}
void postorder() {
postOrderHelper(this->root);
}
NodePtr searchTree(int k) {
return searchTreeHelper(this->root, k);
}
NodePtr minimum(NodePtr node) {
while (node->left != TNULL) {
node = node->left;
}
return node;
}
NodePtr maximum(NodePtr node) {
while (node->right != TNULL) {
node = node->right;
}
return node;
}
NodePtr successor(NodePtr x) {
if (x->right != TNULL) {
return minimum(x->right);
}
NodePtr y = x->parent;
while (y != TNULL && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
NodePtr predecessor(NodePtr x) {
if (x->left != TNULL) {
return maximum(x->left);
}
NodePtr y = x->parent;
while (y != TNULL && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
void leftRotate(NodePtr x) {
NodePtr y = x->right;
x->right = y->left;
if (y->left != TNULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
this->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(NodePtr x) {
NodePtr y = x->left;
x->left = y->right;
if (y->right != TNULL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
this->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// Inserting a node
void insert(int key) {
NodePtr node = new Node;
node->parent = nullptr;
node->data = key;
node->left = TNULL;
node->right = TNULL;
node->color = 1;
NodePtr y = nullptr;
NodePtr x = this->root;
while (x != TNULL) {
y = x;
if (node->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y == nullptr) {
root = node;
} else if (node->data < y->data) {
y->left = node;
} else {
y->right = node;
}
if (node->parent == nullptr) {
node->color = 0;
return;
}
if (node->parent->parent == nullptr) {
return;
}
insertFix(node);
}
NodePtr getRoot() {
return this->root;
}
void deleteNode(int data) {
deleteNodeHelper(this->root, data);
}
void printTree() {
if (root) {
printHelper(this->root, "", true);
}
}
};
int main() {
RedBlackTree V;
V.insert(24);
V.insert(33);
V.insert(42);
V.insert(51);
V.insert(60);
V.insert(40);
V.insert(22);
V.printTree();
cout << endl
<< "After deleting an element" << endl;
V.deleteNode(40);
V.printTree();
}
输出
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
| L----40(RED)
R----60(BLACK)
After deleting an element
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
R----60(BLACK)
// Implementing Red-Black Tree in Java
class Node {
int data;
Node parent;
Node left;
Node right;
int color;
}
public class RedBlackTree {
private Node root;
private Node TNULL;
// Preorder
private void preOrderHelper(Node node) {
if (node != TNULL) {
System.out.print(node.data + " ");
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}
// Inorder
private void inOrderHelper(Node node) {
if (node != TNULL) {
inOrderHelper(node.left);
System.out.print(node.data + " ");
inOrderHelper(node.right);
}
}
// Post order
private void postOrderHelper(Node node) {
if (node != TNULL) {
postOrderHelper(node.left);
postOrderHelper(node.right);
System.out.print(node.data + " ");
}
}
// Search the tree
private Node searchTreeHelper(Node node, int key) {
if (node == TNULL || key == node.data) {
return node;
}
if (key < node.data) {
return searchTreeHelper(node.left, key);
}
return searchTreeHelper(node.right, key);
}
// Balance the tree after deletion of a node
private void fixDelete(Node x) {
Node s;
while (x != root && x.color == 0) {
if (x == x.parent.left) {
s = x.parent.right;
if (s.color == 1) {
s.color = 0;
x.parent.color = 1;
leftRotate(x.parent);
s = x.parent.right;
}
if (s.left.color == 0 && s.right.color == 0) {
s.color = 1;
x = x.parent;
} else {
if (s.right.color == 0) {
s.left.color = 0;
s.color = 1;
rightRotate(s);
s = x.parent.right;
}
s.color = x.parent.color;
x.parent.color = 0;
s.right.color = 0;
leftRotate(x.parent);
x = root;
}
} else {
s = x.parent.left;
if (s.color == 1) {
s.color = 0;
x.parent.color = 1;
rightRotate(x.parent);
s = x.parent.left;
}
if (s.right.color == 0 && s.right.color == 0) {
s.color = 1;
x = x.parent;
} else {
if (s.left.color == 0) {
s.right.color = 0;
s.color = 1;
leftRotate(s);
s = x.parent.left;
}
s.color = x.parent.color;
x.parent.color = 0;
s.left.color = 0;
rightRotate(x.parent);
x = root;
}
}
}
x.color = 0;
}
private void rbTransplant(Node u, Node v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
v.parent = u.parent;
}
private void deleteNodeHelper(Node node, int key) {
Node z = TNULL;
Node x, y;
while (node != TNULL) {
if (node.data == key) {
z = node;
}
if (node.data <= key) {
node = node.right;
} else {
node = node.left;
}
}
if (z == TNULL) {
System.out.println("Couldn't find key in the tree");
return;
}
y = z;
int yOriginalColor = y.color;
if (z.left == TNULL) {
x = z.right;
rbTransplant(z, z.right);
} else if (z.right == TNULL) {
x = z.left;
rbTransplant(z, z.left);
} else {
y = minimum(z.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
} else {
rbTransplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
rbTransplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOriginalColor == 0) {
fixDelete(x);
}
}
// Balance the node after insertion
private void fixInsert(Node k) {
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
leftRotate(k.parent.parent);
}
} else {
u = k.parent.parent.right;
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
leftRotate(k);
}
k.parent.color = 0;
k.parent.parent.color = 1;
rightRotate(k.parent.parent);
}
}
if (k == root) {
break;
}
}
root.color = 0;
}
private void printHelper(Node root, String indent, boolean last) {
if (root != TNULL) {
System.out.print(indent);
if (last) {
System.out.print("R----");
indent += " ";
} else {
System.out.print("L----");
indent += "| ";
}
String sColor = root.color == 1 ? "RED" : "BLACK";
System.out.println(root.data + "(" + sColor + ")");
printHelper(root.left, indent, false);
printHelper(root.right, indent, true);
}
}
public RedBlackTree() {
TNULL = new Node();
TNULL.color = 0;
TNULL.left = null;
TNULL.right = null;
root = TNULL;
}
public void preorder() {
preOrderHelper(this.root);
}
public void inorder() {
inOrderHelper(this.root);
}
public void postorder() {
postOrderHelper(this.root);
}
public Node searchTree(int k) {
return searchTreeHelper(this.root, k);
}
public Node minimum(Node node) {
while (node.left != TNULL) {
node = node.left;
}
return node;
}
public Node maximum(Node node) {
while (node.right != TNULL) {
node = node.right;
}
return node;
}
public Node successor(Node x) {
if (x.right != TNULL) {
return minimum(x.right);
}
Node y = x.parent;
while (y != TNULL && x == y.right) {
x = y;
y = y.parent;
}
return y;
}
public Node predecessor(Node x) {
if (x.left != TNULL) {
return maximum(x.left);
}
Node y = x.parent;
while (y != TNULL && x == y.left) {
x = y;
y = y.parent;
}
return y;
}
public void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
public void rightRotate(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != TNULL) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
public void insert(int key) {
Node node = new Node();
node.parent = null;
node.data = key;
node.left = TNULL;
node.right = TNULL;
node.color = 1;
Node y = null;
Node x = this.root;
while (x != TNULL) {
y = x;
if (node.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y == null) {
root = node;
} else if (node.data < y.data) {
y.left = node;
} else {
y.right = node;
}
if (node.parent == null) {
node.color = 0;
return;
}
if (node.parent.parent == null) {
return;
}
fixInsert(node);
}
public Node getRoot() {
return this.root;
}
public void deleteNode(int data) {
deleteNodeHelper(this.root, data);
}
public void printTree() {
printHelper(this.root, "", true);
}
public static void main(String[] args) {
RedBlackTree V = new RedBlackTree();
V.insert(24);
V.insert(33);
V.insert(42);
V.insert(51);
V.insert(60);
V.insert(40);
V.insert(22);
V.printTree();
System.out.println("\nAfter deleting an element:");
V.deleteNode(40);
V.printTree();
}
}
输出
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
| L----40(RED)
R----60(BLACK)
After deleting an element:
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
R----60(BLACK)
#python program for Red black trees
import sys
# Node creation
class Node():
def __init__(self, item):
self.item = item
self.parent = None
self.left = None
self.right = None
self.color = 1
class RedBlackTree():
def __init__(self):
self.TNULL = Node(0)
self.TNULL.color = 0
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
# Preorder
def pre_order_helper(self, node):
if node != TNULL:
sys.stdout.write(node.item + " ")
self.pre_order_helper(node.left)
self.pre_order_helper(node.right)
# Inorder
def in_order_helper(self, node):
if node != TNULL:
self.in_order_helper(node.left)
sys.stdout.write(node.item + " ")
self.in_order_helper(node.right)
# Postorder
def post_order_helper(self, node):
if node != TNULL:
self.post_order_helper(node.left)
self.post_order_helper(node.right)
sys.stdout.write(node.item + " ")
# Search the tree
def search_tree_helper(self, node, key):
if node == TNULL or key == node.item:
return node
if key < node.item:
return self.search_tree_helper(node.left, key)
return self.search_tree_helper(node.right, key)
# Balancing the tree after deletion
def delete_fix(self, x):
while x != self.root and x.color == 0:
if x == x.parent.left:
s = x.parent.right
if s.color == 1:
s.color = 0
x.parent.color = 1
self.left_rotate(x.parent)
s = x.parent.right
if s.left.color == 0 and s.right.color == 0:
s.color = 1
x = x.parent
else:
if s.right.color == 0:
s.left.color = 0
s.color = 1
self.right_rotate(s)
s = x.parent.right
s.color = x.parent.color
x.parent.color = 0
s.right.color = 0
self.left_rotate(x.parent)
x = self.root
else:
s = x.parent.left
if s.color == 1:
s.color = 0
x.parent.color = 1
self.right_rotate(x.parent)
s = x.parent.left
if s.right.color == 0 and s.right.color == 0:
s.color = 1
x = x.parent
else:
if s.left.color == 0:
s.right.color = 0
s.color = 1
self.left_rotate(s)
s = x.parent.left
s.color = x.parent.color
x.parent.color = 0
s.left.color = 0
self.right_rotate(x.parent)
x = self.root
x.color = 0
def __rb_transplant(self, u, v):
if u.parent == None:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
# Node deletion
def delete_node_helper(self, node, key):
z = self.TNULL
while node != self.TNULL:
if node.item == key:
z = node
if node.item <= key:
node = node.right
else:
node = node.left
if z == self.TNULL:
print("Cannot find key in the tree")
return
y = z
y_original_color = y.color
if z.left == self.TNULL:
x = z.right
self.__rb_transplant(z, z.right)
elif (z.right == self.TNULL):
x = z.left
self.__rb_transplant(z, z.left)
else:
y = self.minimum(z.right)
y_original_color = y.color
x = y.right
if y.parent == z:
x.parent = y
else:
self.__rb_transplant(y, y.right)
y.right = z.right
y.right.parent = y
self.__rb_transplant(z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == 0:
self.delete_fix(x)
# Balance the tree after insertion
def fix_insert(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.right_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.left_rotate(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self.left_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.right_rotate(k.parent.parent)
if k == self.root:
break
self.root.color = 0
# Printing the tree
def __print_helper(self, node, indent, last):
if node != self.TNULL:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "
s_color = "RED" if node.color == 1 else "BLACK"
print(str(node.item) + "(" + s_color + ")")
self.__print_helper(node.left, indent, False)
self.__print_helper(node.right, indent, True)
def preorder(self):
self.pre_order_helper(self.root)
def inorder(self):
self.in_order_helper(self.root)
def postorder(self):
self.post_order_helper(self.root)
def searchTree(self, k):
return self.search_tree_helper(self.root, k)
def minimum(self, node):
while node.left != self.TNULL:
node = node.left
return node
def maximum(self, node):
while node.right != self.TNULL:
node = node.right
return node
def successor(self, x):
if x.right != self.TNULL:
return self.minimum(x.right)
y = x.parent
while y != self.TNULL and x == y.right:
x = y
y = y.parent
return y
def predecessor(self, x):
if (x.left != self.TNULL):
return self.maximum(x.left)
y = x.parent
while y != self.TNULL and x == y.left:
x = y
y = y.parent
return y
def left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def insert(self, key):
node = Node(key)
node.parent = None
node.item = key
node.left = self.TNULL
node.right = self.TNULL
node.color = 1
y = None
x = self.root
while x != self.TNULL:
y = x
if node.item < x.item:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.item < y.item:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.fix_insert(node)
def get_root(self):
return self.root
def delete_node(self, item):
self.delete_node_helper(self.root, item)
def print_tree(self):
self.__print_helper(self.root, "", True)
if __name__ == "__main__":
V = RedBlackTree()
V.insert(24)
V.insert(33)
V.insert(42)
V.insert(51)
V.insert(60)
V.insert(40)
V.insert(22)
V.print_tree()
print("\nAfter deleting an element")
V.delete_node(40)
V.print_tree()
输出
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
| L----40(RED)
R----60(BLACK)
After deleting an element
R----33(BLACK)
L----24(BLACK)
| L----22(RED)
R----51(RED)
L----42(BLACK)
R----60(BLACK)