红黑树
红黑树是平衡二叉搜索树的另一种类型，它有两种颜色的节点：红色和黑色。它是一种自平衡二叉搜索树，利用这两种颜色在插入和删除操作中保持平衡。因此，在红黑树操作期间，内存使用 1 位存储空间来容纳每个节点的颜色信息。
在红黑树（也称为 RB 树）中，为节点分配颜色时需要遵循不同的条件。
根节点始终为黑色。
任何两个相邻节点都不能是红色。
树中的每条路径（从根节点到叶节点）都必须具有相同数量的黑色节点。
尽管 AVL 树比 RB 树更平衡，并且 AVL 树中的平衡算法比 RB 树更严格，但通过 RB 树可以更高效地执行多次更快的插入和删除操作。
图：红黑树
红黑树的基本操作
红黑树上的操作包含二叉搜索树上通常执行的所有基本操作。红黑树的一些基本操作包括 −
插入
删除
查找
插入操作
红黑树的插入操作遵循与二叉搜索树相同的插入算法。元素插入遵循二叉搜索属性，此外，节点颜色编码为红色和黑色，以根据红黑树属性平衡树。
按照以下步骤，在保持二叉搜索树和红黑树属性的情况下，将元素插入红黑树。
情况 1 − 检查树是否为空；将当前节点作为根节点，如果为空，则将其着色为黑色。
情况 2 − 但如果树不为空，我们创建一个新节点并将其着色为红色。这里我们面临两种不同的情况 −
如果新节点的父节点是黑色节点，则退出操作，树保持原样。
如果此新节点的父节点为红色，且其父节点的兄弟节点为黑色或不存在，则进行适当的旋转并相应地重新着色。
如果此新节点的父节点为红色，且其父节点的兄弟节点为红色，则将父节点、兄弟节点和祖父母节点重新着色为黑色。仅当祖父母节点不是根节点时才重新着色；如果祖父母节点是根节点，则仅重新着色其父节点和兄弟节点。
示例
为了详细了解插入操作 −，我们构建一个包含前 7 个整数的 RB 树。
检查树是否为空，因此添加的第一个节点是根节点，并标记为黑色。
现在，树不为空，因此我们创建一个新节点，并将下一个整数标记为红色。
这些节点不违反二叉搜索树和 RB 树的属性，因此我们继续添加另一个节点。
树不为空；我们创建一个新的红色节点，并将下一个整数标记为红色。但新节点的父节点不是黑色节点，
该树现在同时违反了二叉搜索树和RB树的属性；由于父节点的兄弟节点为 NULL，我们应用适当的旋转并重新着色节点。
现在 RB 树属性已恢复，我们向树中添加另一个节点 −
该树再次违反了 RB 树的平衡属性，因此我们检查父节点的兄弟节点颜色（在本例中为红色），因此我们只需重新着色父节点和兄弟节点即可。
接下来我们插入元素 5，这使得树再次违反 RB 树平衡属性再次。
由于兄弟节点为 NULL，我们应用适当的旋转并重新着色。
现在，我们插入元素 6，但违反了红黑树的属性，需要应用其中一种插入情况减法。
父节点的兄弟节点为红色，因此我们重新着色父节点、父节点的兄弟节点和祖父母节点，因为祖父母节点不是根节点。
现在，我们添加最后一个元素 7，但这个新节点的父节点是红色的。
由于父节点的兄弟节点为 NULL，我们应用适当的旋转（RR 旋转）
最终的 RB 树已完成。
删除操作
红黑树上的删除操作必须以恢复二叉搜索树和红黑树的所有属性的方式执行。按照以下步骤在红黑树上执行删除操作 −
首先，我们根据二叉搜索树的属性进行删除操作。
情况 1 − 如果要删除的节点或其父节点为红色，则删除该节点。
情况 2 − 如果节点是双黑，则删除双黑节点（当要删除的节点是黑色叶子节点时会发生双黑，因为它会将同样被视为黑色节点的 NULL 节点相加）。
情况 3 −如果双黑节点的兄弟节点也是黑色节点，且其子节点也是黑色，则按照以下步骤 −
移除双黑节点
将其父节点重新着色为黑色（如果父节点是红色节点，则变为黑色；如果父节点已经是黑色节点，则变为双黑节点）
将父节点的兄弟节点重新着色为红色
如果仍然存在双黑节点，则应用其他情况。
情况 4 −如果双黑节点的兄弟节点为红色，则执行以下步骤 −
交换父节点及其兄弟节点的颜色。
沿双黑节点方向旋转父节点
重新应用其他合适的情况。
情况 5 − 如果双黑节点的兄弟节点是黑色节点，但其兄弟节点中最靠近双黑节点的子节点是红色，则执行以下步骤 −
交换双黑节点的兄弟节点和该兄弟节点的子节点的颜色
将兄弟节点旋转至与双黑节点相反的方向（例如，如果双黑节点是右子节点，则进行左旋转，反之亦然）
应用情况 6。
情况 6 −如果双黑节点的兄弟节点是黑色节点，但其兄弟节点中距离双黑节点较远的子节点是红色，则执行以下步骤 −
交换双黑节点的父节点和兄弟节点的颜色
将父节点沿双黑节点的方向旋转（例如，如果双黑节点是右子节点，则进行右旋转，反之亦然）
移除双黑节点
将红色子节点的颜色更改为黑色。
示例
考虑上面构造的相同红黑树，让我们从树中删除一些元素。
删除元素4、5、3 从树中删除。
要删除元素 4，我们先执行二分查找删除操作。
执行二分查找删除操作后，RB 树的属性未受影响，因此树保持原样。
然后，我们使用二分查找删除操作删除元素 5
但是执行二分查找删除操作后，RB 树的属性被破坏，即树中的所有路径并不包含相同数量的黑色节点；因此我们交换颜色来平衡树。
然后，我们从得到的树中删除节点 3 −
应用二分查找删除法，我们正常删除节点 3，因为它是叶节点。由于 3 是黑色节点，因此我们得到一个双黑节点。
我们应用情况 3 删除，因为双黑节点的兄弟节点是黑色，并且它的子节点也是黑色。这里，我们移除双黑节点，并重新着色其父节点和兄弟节点。
所有所需节点均已删除，红黑树属性保持不变。
搜索操作
红黑树的搜索操作遵循与二叉搜索树相同的算法。遍历树，并将每个节点与要搜索的键元素进行比较；如果找到，则返回搜索成功。否则，返回搜索失败。
完整实现
以下是各种编程语言中红黑树的完整实现 −
// 红黑树算法的 C++ 程序
#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);
}
// 删除后平衡树
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);
}
}
// 插入后平衡树
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;
}
// 插入节点
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)
// 在 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 + " ");
}
}
// 搜索树
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);
}
// 删除节点后平衡树
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);
}
}
// 插入后平衡节点
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("
After 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)
# 后序
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 + " ")
# 搜索树
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)
# 删除后平衡树
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
# 节点删除
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)
# 插入后平衡树
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("
After 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)
