# 紅黑樹 > 原文： [https://www.programiz.com/dsa/red-black-tree](https://www.programiz.com/dsa/red-black-tree) #### 在本教程中，您將學習什么是紅黑樹。 此外，您還將找到在 C，C++ ，Java 和 Python 的紅黑樹上執行的各種操作的工作示例。 紅黑樹是一種自平衡二叉搜索樹，其中每個節點都包含一個額外的位，用于表示該節點的顏色，紅色還是黑色。 一棵紅黑樹滿足以下屬性： 1. **紅色/黑色屬性**：每個節點都是紅色或黑色。 2. **根屬性**：根是黑色的。 3. **葉子屬性**：每片葉子（`NIL`）是黑色的。 4. **紅色屬性**：如果紅色節點具有子代，則子代始終為黑色。 5. **深度屬性**：對于每個節點，從此節點到其任何后代葉子的任何簡單路徑都具有相同的黑深度（黑節點的數量）。 紅黑樹的一個示例是：  紅黑樹 每個節點具有以下屬性： * 顏色 * 鍵 * 左子級 * 右子級 * 父級（根節點除外） * * * **紅黑樹如何保持自我平衡的性質？** 紅黑顏色用于平衡樹。 節點顏色的限制確保從根到葉的任何簡單路徑的長度都不會超過其他路徑的兩倍。 它有助于維持紅黑樹的自平衡特性。 * * * ## 紅黑樹上的操作 可以在紅黑樹上執行的各種操作包括： ### 旋轉紅黑樹中的子樹 在旋轉操作中，子樹的節點位置互換。 旋轉操作用于在其他操作（例如插入和刪除）破壞紅黑樹的屬性時維護它們。 輪播有兩種類型： * * * ### 向左旋轉 在向左旋轉時，右側節點的排列將轉換為左側節點的排列。 **算法** 1. 令初始樹為：  初始樹 2. 如果`y`具有左子樹，則將`x`分配為`y`的左子樹的父樹。  將`x`分配為`y`的左子樹的父級 3. 如果`x`的父級是`NULL`，則將`y`作為樹的根。 4. 否則，如果`x`是`p`的左子代，則將`y`設為`p`的左子代。 5. 否則，將`y`分配為`p`的右子元素。  將`x`的父級更改為`y`的父級 6. 將`y`設為`x`的父代。  將`y`指定為`x`的父代。 * * * ### 向右旋轉 在向右旋轉時，左側節點的排列將轉換為右側節點的排列。 1. 令初始樹為：  初始樹 2. 如果`x`具有右子樹，則將`y`分配為`x`的右子樹的父樹。  將`y`分配為`x` 的右子樹的父級 3. 如果`y`的父級為`NULL`，則將`x`作為樹的根。 4. 否則，如果`y`是其父級`p`的右子，則將`x`作為`p`的右子。 5. 否則，將`x`分配為`p`的左子元素。  將`y`的父級指定為`x`的父級 6. 使`x`為`y`的父代。  將`x`分配為`y`的父項 * * * ### 左右旋轉 在左右旋轉時，首先將布置向左移動，然后向右移動。 1. 在`x-y`上向左旋轉。  向左旋轉`x-y` 2. 在`y-z`上向右旋轉。  向右旋轉`z-y` 在左右旋轉時，排列首先移至右側，然后移至左側。 1. 在`x-y`上向右旋轉。  右旋轉`x-y` 2. 在`z-y`上向左旋轉。  向左旋轉`z-y` * * * ### 將元素插入紅黑樹 插入新節點時，新節點始終作為紅色節點插入。 插入新節點后，如果樹違反了紅黑樹的屬性，則執行以下操作。 1. 重新著色 2. 重新旋轉 * * * ### 插入節點的算法 按照以下步驟將新元素插入到紅黑樹中： 1. 令`y`為葉子（即`NIL`），`x`為樹的根。 2. 檢查樹是否為空（即`x`是否為`NIL`）。 如果是，請插入`newNode`作為根節點，并將其著色為黑色。 3. 否則，請重復以下步驟，直到達到葉子（`NIL`）。 1. 比較`newKey`與`rootKey`。 2. 如果`newKey`大于`rootKey`，則遍歷右側子樹。 3. 否則，遍歷左子樹。 4. 將葉子的父級分配為`newNode`的父級。 5. 如果`leafKey`大于`newKey`，則將`newNode`設置為`rightChild`。 6. 否則，將`newNode`設置為`leftChild`。 7. 在`newNode`的左側分配`NULL`，在右邊分配子級。 8. 為`newNode`分配紅色。 9. 調用`InsertFix`算法來維護紅黑樹的屬性（如果違反）。 * * * **為什么新插入的節點在紅黑樹中總是紅色？** 這是因為插入紅色節點不會違反紅黑樹的`depth`屬性。 如果將紅色節點附加到紅色節點，則會違反該規則，但是比通過違反`depth`屬性引入的問題更容易解決此問題。 * * * ### 插入后保持紅黑屬性的算法 如果`newNode`的插入違反了此屬性，則此算法用于維護紅黑樹的屬性。 1. 進行以下操作，直到`newNode p`的父級為紅色。 2. 如果`p`是`z`的`grandParent gP`的左子級，請執行以下操作。 **情況一**： 1. 如果`z`的`gP`的右子色為紅色，則將`gP`的兩個子級分別設置為黑色和紅色。 2. 將`gP`分配給`newNode`。 **情況 II**： 3. 否則，如果`newNode`是`p`的右子代，則將`p`分配給`newNode`。 4. 向左旋轉`newNode`。 **情況 III**： 5. 將`p`的顏色設置為黑色，將`gP`的顏色設置為紅色。 6. 右旋`gP`。 3. 否則，請執行以下操作。 1. 如果`z`的`gP`的左子色為紅色，則將`gP`的兩個子色分別設為黑色和紅色。 2. 將`gP`分配給`newNode`。 3. 否則，如果`newNode`是`p`的左子代，則將`p`分配給`newNode`和向右旋轉`newNode`。 4. 將`p`的顏色設置為黑色，將`gP`的顏色設置為紅色。 5. 左旋`gP`。 4. 將樹的根設置為黑色。 * * * ### 從紅黑樹中刪除元素 此操作從樹中刪除節點。 刪除節點后，再次保留紅黑屬性。 * * * ### 刪除節點的算法 1. 將`nodeToBeDeleted`的顏色保存在`origrinalColor`中。 2. 如果`nodeToBeDeleted`的左子級是`NULL` 1. 將`nodeToBeDeleted`的右子代分配給`x`。 2. 用`x`移植`nodeToBeDeleted`。 3. 否則，如果`nodeToBeDeleted`的右子對象是`NULL` 1. 將`nodeToBeDeleted`的左子級分配到`x`中。 2. 用`x`移植`nodeToBeDeleted`。 4. 其他 1. 將`noteToBeDeleted`的右子樹的最小值分配到`y`中。 2. 將`sum`的顏色保存在`originalColor`中。 3. 將`y`的`rightChild`分配到`x`中。 4. 如果`y`是`nodeToBeDeleted`的子級，則將`x`的父級設置為`y`。 5. 否則，將`y`移植為`y`的`rightChild`。 6. 將`sum`移植到`nodeToBeDeleted`中。 7. 使用`originalColor`設置`y`的顏色。 5. 如果`originalColor`為黑色，則調用`DeleteFix(x)`。 * * * ### 刪除后保持紅黑屬性的算法 當刪除黑色節點時會執行此算法，因為它違反了紅黑樹的黑色深度屬性。 通過假定節點`x`（占據`y`的原始位置）具有額外的黑色來糾正此沖突。 這使得節點`x`既不是紅色的，也不是黑色的。 它是雙黑色或黑色和紅色。 這違反了紅黑色屬性。 但是，`x`的顏色屬性未更改，而是在指向節點的`x`的表示中表示了額外的黑色。 如果多余的黑色可以去除 1. 它到達根節點。 2. 如果`x`指向紅黑節點。 在這種情況下，`x`被涂成黑色。 3. 進行適當的旋轉和重新著色。 以下算法保留了紅黑樹的屬性。 1. 執行以下操作，直到`x`不是樹的根并且`x`的顏色為黑色 2. 如果`x`是其父級的左子級， 1. 將`w`分配給`x`的同級。 2. 如果`x`的父級的右子是紅色，則 **情況 I**： 1. 將`x`的父級的右子級的顏色設置為黑色。 2. 將`x`的父級顏色設置為紅色。 3. 左旋轉`x`的父級。 4. 將`x`的父級的`rightChild`分配給`w`。 3. 如果`w`的右側和`leftChild`的顏色均為黑色，則 **情況 II**： 1. 將`w`的顏色設置為紅色 2. 將`x`的父級分配給`x`。 4. 否則，如果`w`的`rightChild`的顏色是黑色 **情況 III**： 1. 將`w`的`leftChild`的顏色設置為黑色 2. 將`w`的顏色設置為紅色 3. 向右旋轉`w`。 4. 將`x`的父級的`rightChild`分配給`w`。 5. 如果以上情況均未發生，請執行以下操作。 **情況 IV**： 1. 將`w`的顏色設置為`x`的父代的顏色。 2. 將`x`的父級的顏色設置為黑色。 3. 將`w`的右子元素的顏色設置為黑色。 4. 左旋轉`x`的父級。 5. 將`x`設置為樹的根。 3. 其他與上述相同，將右側更改為左側，反之亦然。 4. 將`x`的顏色設置為黑色。 * * * 有關示例的更多說明，請參見[插入](/dsa/insertion-in-a-red-black-tree)和[刪除](/deletion-from-a-red-black-tree)操作。 * * * ## Python，Java 和 C/C++ 示例 ```py # Implementing Red-Black Tree in Python 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__": bst = RedBlackTree() bst.insert(55) bst.insert(40) bst.insert(65) bst.insert(60) bst.insert(75) bst.insert(57) bst.print_tree() print("\nAfter deleting an element") bst.delete_node(40) bst.print_tree() ``` ```java // 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 bst = new RedBlackTree(); bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); System.out.println("\nAfter deleting:"); bst.deleteNode(40); bst.printTree(); } } ``` ```c // Implementing Red-Black Tree in C #include <stdio.h> #include <stdlib.h> enum nodeColor { RED, BLACK }; struct rbNode { int data, color; struct rbNode *link[2]; }; struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) { struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link[0] = newnode->link[1] = NULL; return newnode; } // Insert an node void insertion(int data) { struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr; int dir[98], ht = 0, index; ptr = root; if (!root) { root = createNode(data); return; } stack[ht] = root; dir[ht++] = 0; while (ptr != NULL) { if (ptr->data == data) { printf("Duplicates Not Allowed!!\n"); return; } index = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; ptr = ptr->link[index]; dir[ht++] = index; } stack[ht - 1]->link[index] = newnode = createNode(data); while ((ht >= 3) && (stack[ht - 1]->color == RED)) { if (dir[ht - 2] == 0) { yPtr = stack[ht - 2]->link[1]; if (yPtr != NULL && yPtr->color == RED) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 0) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[1]; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; stack[ht - 2]->link[0] = yPtr; } xPtr = stack[ht - 2]; xPtr->color = RED; yPtr->color = BLACK; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } else { yPtr = stack[ht - 2]->link[0]; if ((yPtr != NULL) && (yPtr->color == RED)) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 1) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; stack[ht - 2]->link[1] = yPtr; } xPtr = stack[ht - 2]; yPtr->color = BLACK; xPtr->color = RED; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } } root->color = BLACK; } // Delete a node void deletion(int data) { struct rbNode *stack[98], *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir[98], ht = 0, diff, i; enum nodeColor color; if (!root) { printf("Tree not available\n"); return; } ptr = root; while (ptr != NULL) { if ((data - ptr->data) == 0) break; diff = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; dir[ht++] = diff; ptr = ptr->link[diff]; } if (ptr->link[1] == NULL) { if ((ptr == root) && (ptr->link[0] == NULL)) { free(ptr); root = NULL; } else if (ptr == root) { root = ptr->link[0]; free(ptr); } else { stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0]; } } else { xPtr = ptr->link[1]; if (xPtr->link[0] == NULL) { xPtr->link[0] = ptr->link[0]; color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) { root = xPtr; } else { stack[ht - 1]->link[dir[ht - 1]] = xPtr; } dir[ht] = 1; stack[ht++] = xPtr; } else { i = ht++; while (1) { dir[ht] = 0; stack[ht++] = xPtr; yPtr = xPtr->link[0]; if (!yPtr->link[0]) break; xPtr = yPtr; } dir[i] = 1; stack[i] = yPtr; if (i > 0) stack[i - 1]->link[dir[i - 1]] = yPtr; yPtr->link[0] = ptr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = ptr->link[1]; if (ptr == root) { root = yPtr; } color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; } } if (ht < 1) return; if (ptr->color == BLACK) { while (1) { pPtr = stack[ht - 1]->link[dir[ht - 1]]; if (pPtr && pPtr->color == RED) { pPtr->color = BLACK; break; } if (ht < 2) break; if (dir[ht - 2] == 0) { rPtr = stack[ht - 1]->link[1]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 0; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[1]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) { qPtr = rPtr->link[0]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[0] = qPtr->link[1]; qPtr->link[1] = rPtr; rPtr = stack[ht - 1]->link[1] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[1]->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } else { rPtr = stack[ht - 1]->link[0]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 1; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[0]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) { qPtr = rPtr->link[1]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[1] = qPtr->link[0]; qPtr->link[0] = rPtr; rPtr = stack[ht - 1]->link[0] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[0]->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } ht--; } } } // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) { if (node) { inorderTraversal(node->link[0]); printf("%d ", node->data); inorderTraversal(node->link[1]); } return; } // Driver code int main() { int ch, data; while (1) { printf("1\. Insertion\t2\. Deletion\n"); printf("3\. Traverse\t4\. Exit"); printf("\nEnter your choice:"); scanf("%d", &ch); switch (ch) { case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf("\n"); break; case 4: exit(0); default: printf("Not available\n"); break; } printf("\n"); } return 0; } ``` ```cpp // Implementing Red-Black Tree in 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); } // 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 bst; bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); cout << endl << "After deleting" << endl; bst.deleteNode(40); bst.printTree(); } ``` * * * ## 紅黑樹應用 1. 實現有限圖 2. 要實現 Java 包：`java.util.TreeMap`和`java.util.TreeSet` 3. 要在 C++ 中實現標準模板庫（STL）：多集，映射，多映射 4. 在 Linux 內核中