插入紅黑樹 · Programiz 中文系列教程

# 插入紅黑樹 > 原文： [https://www.programiz.com/dsa/insertion-in-a-red-black-tree](https://www.programiz.com/dsa/insertion-in-a-red-black-tree) #### 在本教程中，您將學習如何將新節點插入到紅黑樹中。此外，您還將找到在 C，C++ ，Java 和 Python 的紅黑樹上執行插入的工作示例。紅黑樹是一種自平衡二叉搜索樹，其中每個節點都包含一個額外的位，用于表示該節點的顏色，紅色還是黑色。閱讀本文之前，請參考[紅黑樹](/dsa/red-black-tree)上的文章。插入新節點時，新節點始終作為紅色節點插入。插入新節點后，如果樹違反了紅黑樹的屬性，則執行以下操作。 1. 重新著色 2. 重新旋轉 * * * ## 插入新節點的算法按照以下步驟將新元素插入到紅黑樹中： 1. `newNode`為： ![New Node](https://img.kancloud.cn/a4/6e/a46e543664f23a507f839f0af4ba035a_232x260.png "new node to be inserted") 新節點 2. 令`y`為葉子（即`NIL`），`x`為樹的根。新節點將插入下面的樹中。 ![insertion in red black tree](https://img.kancloud.cn/24/6d/246d89b2edb2a2e34b59722cc51aae71_1100x688.png "the initial tree") 初始樹 3. 檢查樹是否為空（即`x`是否為`NIL`）。如果是，請插入`newNode`作為根節點，并將其著色為黑色。 4. 否則，請重復以下步驟，直到達到葉子（`NIL`）。 1. 比較`newKey`與`rootKey`。 2. 如果`newKey`大于`rootKey`，則遍歷右側子樹。 3. 否則，遍歷左子樹。 ![insertion in red black tree](https://img.kancloud.cn/04/15/041555a76d4f35885058cb8ef1bf130c_1052x800.png "path leading to the node where newNode is to be inserted") 指向要在其中插入`newNode`的節點的路徑 5. 將葉子的父級分配為`newNode`的父級。 6. 如果`leafKey`大于`newKey`，則將`newNode`設為`rightChild`。 7. 否則，將`newNode`設置為`leftChild`。 ![insertion in red black tree](https://img.kancloud.cn/88/a5/88a5de1a4fb48f846db578c3543e141d_304x360.png "new node inserted") 插入了新節點 8. 在左側分配`NULL`，在`newNode`分配`rightChild`。 9. 為`newNode`分配紅色。 ![insertion in red black tree](https://img.kancloud.cn/16/c6/16c67aa00aef29154f22f2bc2a03d772_304x488.png "set the color of the newNode red and assign null to the children.") 將`newNode`的顏色設置為紅色，并為子代分配空值 10. 調用`InsertFix`算法來維護紅黑樹的屬性（如果違反）。 * * * **為什么新插入的節點在紅黑樹中總是紅色？** 這是因為插入紅色節點不會違反紅黑樹的`depth`屬性。如果將紅色節點附加到紅色節點，則會違反該規則，但是比通過違反`depth`屬性引入的問題更容易解決此問題。 * * * ## 插入后保持紅黑屬性的算法如果插入`newNode`違反了該屬性，則此算法用于維護紅黑樹的屬性。 1. 執行以下操作，直到`newNode p`的父代變為紅色。 2. 如果`p`是`newNode`的`grandParent gP`的左子級，請執行以下操作。 **情況一**： 1. 如果`newNode`的`gP`的右子級的顏色是紅色，則將`gP`的子級的顏色都設置為黑色，將`gP`的顏色都設置為紅色。 ![insertion in a red-black tree](https://img.kancloud.cn/88/c6/88c6353d6391697f7b352a5b919dfd37_964x630.png "color change") 顏色更改 2. 將`gP`分配給`newNode`。 ![insertion in a red-black tree](https://img.kancloud.cn/37/f5/37f5ba42db68c0251b51a000a541d3d4_700x590.png "reassigning newNode") 重新分配`newNode` **情況 II**： 3. （在繼續此步驟之前，將檢查`while`循環。如果不滿足條件，則循環會中斷。）否則，如果`newNode`是`p`的右子代，則將`p`分配給[ `newNode`。 ![insertion in a red-black tree](https://img.kancloud.cn/75/a7/75a7ebc46694093326cee5f8c852020e_632x696.png "assigning parent of newNode as newNode") 將`newNode`的父級分配為`newNode` 4. 左旋轉`newNode`。 ![Insertion in a red-black tree](https://img.kancloud.cn/64/4f/644f8058cc6efb10717eb2ba4a27b46e_970x620.png "Left Rotate") 左旋轉 **情況 III**： 5. （在繼續此步驟之前，檢查循環。如果不滿足條件，則循環中斷。）將`p`的顏色設置為黑色，將`gP`的顏色設置為紅色。 ![insertion in a redblack tree](https://img.kancloud.cn/db/13/db136223c5989bc8cfaec042a56bebad_1270x604.png "color change") 顏色更改 6. 向右旋轉`gP`。 ![insertion in a red-black tree](https://img.kancloud.cn/67/24/6724de3dcbefa5d4de85bd98933851be_1068x604.png "right rotate") 右旋 3. 否則，請執行以下操作。 1. 如果`z`的`gP`的左子項的顏色是紅色，請將`gP`的子項的顏色都設置為黑色，將`gP`的顏色都設置為紅色。 2. 將`gP`分配給`newNode`。 3. 否則，如果`newNode`是`p`的左子代，則將`p`分配給`newNode`并向右旋轉`newNode`。 4. 將`p`的顏色設置為黑色，將`gP`的顏色設置為紅色。 5. 左旋轉`gP`。 4. （從`while`循環中退出后執行此步驟。）將樹的根設置為黑色。 ![insertion in a red-black tree](https://img.kancloud.cn/5e/2c/5e2ce4ca6c38e90d2c28353fba2992e3_634x468.png "set root's color black") 將根的顏色設置為黑色最終的樹如下所示： ![insertion in a red-black tree](https://img.kancloud.cn/43/7c/437c0c7d5e7c76d0641dc8a8db6c1ee5_1064x756.png "final 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) # 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 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() ``` ```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; } // 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 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(); } } ``` ```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(); } ```