原文： https://www.programiz.com/dsa/insertion-in-a-red-black-tree

在本教程中，您将学习如何将新节点插入到红黑树中。 此外，您还将找到在 C，C++ ，Java 和 Python 的红黑树上执行插入的工作示例。

红黑树是一种自平衡二叉搜索树，其中每个节点都包含一个额外的位，用于表示该节点的颜色，红色还是黑色。

阅读本文之前，请参考红黑树上的文章。

插入新节点时，新节点始终作为红色节点插入。 插入新节点后，如果树违反了红黑树的属性，则执行以下操作。

  1. 重新着色
  2. 重新旋转

插入新节点的算法

按照以下步骤将新元素插入到红黑树中：

  1. newNode为：
    插入红黑树 - 图1
    新节点

  2. 令y为叶子（即NIL），x为树的根。 新节点将插入下面的树中。
    插入红黑树 - 图2
    初始树

  3. 检查树是否为空（即x是否为NIL）。 如果是，请插入newNode作为根节点，并将其着色为黑色。

  4. 否则，请重复以下步骤，直到达到叶子（NIL）。

    1. 比较newKey与rootKey。

    2. 如果newKey大于rootKey，则遍历右侧子树。

    3. 否则，遍历左子树。
      插入红黑树 - 图3
      指向要在其中插入newNode的节点的路径

  5. 将叶子的父级分配为newNode的父级。

  6. 如果leafKey大于newKey，则将newNode设为rightChild。

  7. 否则，将newNode设置为leftChild。
    插入红黑树 - 图4
    插入了新节点

  8. 在左侧分配NULL，在newNode分配rightChild。

  9. 为newNode分配红色。
    插入红黑树 - 图5
    将newNode的颜色设置为红色，并为子代分配空值

  10. 调用InsertFix算法来维护红黑树的属性（如果违反）。

为什么新插入的节点在红黑树中总是红色？

这是因为插入红色节点不会违反红黑树的depth属性。

如果将红色节点附加到红色节点，则会违反该规则，但是比通过违反depth属性引入的问题更容易解决此问题。

插入后保持红黑属性的算法

如果插入newNode违反了该属性，则此算法用于维护红黑树的属性。

  1. 执行以下操作，直到newNode p的父代变为红色。

  2. 如果p是newNode的grandParent gP的左子级，请执行以下操作。
    情况一：

    1. 如果newNode的gP的右子级的颜色是红色，则将gP的子级的颜色都设置为黑色，将gP的颜色都设置为红色。
      插入红黑树 - 图6
      颜色更改

    2. 将gP分配给newNode。
      插入红黑树 - 图7
      重新分配newNode
      情况 II：

    3. （在继续此步骤之前，将检查while循环。如果不满足条件，则循环会中断。）
      否则，如果newNode是p的右子代，则将p分配给[ newNode。
      插入红黑树 - 图8
      将newNode的父级分配为newNode

    4. 左旋转newNode。
      插入红黑树 - 图9
      左旋转
      情况 III：

    5. （在继续此步骤之前，检查循环。如果不满足条件，则循环中断。）
      将p的颜色设置为黑色，将gP的颜色设置为红色。
      插入红黑树 - 图10
      颜色更改

    6. 向右旋转gP。
      插入红黑树 - 图11
      右旋

  3. 否则，请执行以下操作。

    1. 如果z的gP的左子项的颜色是红色，请将gP的子项的颜色都设置为黑色，将gP的颜色都设置为红色。
    2. 将gP分配给newNode。
    3. 否则，如果newNode是p的左子代，则将p分配给newNode并向右旋转newNode。
    4. 将p的颜色设置为黑色，将gP的颜色设置为红色。
    5. 左旋转gP。
  4. （从while循环中退出后执行此步骤。）
    将树的根设置为黑色。
    插入红黑树 - 图12
    将根的颜色设置为黑色

最终的树如下所示：

插入红黑树 - 图13

最终的树

Python，Java 和 C/C++ 示例

  1. # Implementing Red-Black Tree in Python
  3. import sys
  5. # Node creation
  6. class Node():
  7.     def __init__(self, item):
  8.         self.item = item
  9.         self.parent = None
  10.         self.left = None
  11.         self.right = None
  12.         self.color = 1
  14. class RedBlackTree():
  15.     def __init__(self):
  16.         self.TNULL = Node(0)
  17.         self.TNULL.color = 0
  18.         self.TNULL.left = None
  19.         self.TNULL.right = None
  20.         self.root = self.TNULL
  22.     # Preorder
  23.     def pre_order_helper(self, node):
  24.         if node != TNULL:
  25.             sys.stdout.write(node.item + " ")
  26.             self.pre_order_helper(node.left)
  27.             self.pre_order_helper(node.right)
  29.     # Inorder
  30.     def in_order_helper(self, node):
  31.         if node != TNULL:
  32.             self.in_order_helper(node.left)
  33.             sys.stdout.write(node.item + " ")
  34.             self.in_order_helper(node.right)
  36.     # Postorder
  37.     def post_order_helper(self, node):
  38.         if node != TNULL:
  39.             self.post_order_helper(node.left)
  40.             self.post_order_helper(node.right)
  41.             sys.stdout.write(node.item + " ")
  43.     # Search the tree
  44.     def search_tree_helper(self, node, key):
  45.         if node == TNULL or key == node.item:
  46.             return node
  48.         if key < node.item:
  49.             return self.search_tree_helper(node.left, key)
  50.         return self.search_tree_helper(node.right, key)
  52.     # Balance the tree after insertion
  53.     def fix_insert(self, k):
  54.         while k.parent.color == 1:
  55.             if k.parent == k.parent.parent.right:
  56.                 u = k.parent.parent.left
  57.                 if u.color == 1:
  58.                     u.color = 0
  59.                     k.parent.color = 0
  60.                     k.parent.parent.color = 1
  61.                     k = k.parent.parent
  62.                 else:
  63.                     if k == k.parent.left:
  64.                         k = k.parent
  65.                         self.right_rotate(k)
  66.                     k.parent.color = 0
  67.                     k.parent.parent.color = 1
  68.                     self.left_rotate(k.parent.parent)
  69.             else:
  70.                 u = k.parent.parent.right
  72.                 if u.color == 1:
  73.                     u.color = 0
  74.                     k.parent.color = 0
  75.                     k.parent.parent.color = 1
  76.                     k = k.parent.parent
  77.                 else:
  78.                     if k == k.parent.right:
  79.                         k = k.parent
  80.                         self.left_rotate(k)
  81.                     k.parent.color = 0
  82.                     k.parent.parent.color = 1
  83.                     self.right_rotate(k.parent.parent)
  84.             if k == self.root:
  85.                 break
  86.         self.root.color = 0
  88.     # Printing the tree
  89.     def __print_helper(self, node, indent, last):
  90.         if node != self.TNULL:
  91.             sys.stdout.write(indent)
  92.             if last:
  93.                 sys.stdout.write("R----")
  94.                 indent += "     "
  95.             else:
  96.                 sys.stdout.write("L----")
  97.                 indent += "|    "
  99.             s_color = "RED" if node.color == 1 else "BLACK"
  100.             print(str(node.item) + "(" + s_color + ")")
  101.             self.__print_helper(node.left, indent, False)
  102.             self.__print_helper(node.right, indent, True)
  104.     def preorder(self):
  105.         self.pre_order_helper(self.root)
  107.     def inorder(self):
  108.         self.in_order_helper(self.root)
  110.     def postorder(self):
  111.         self.post_order_helper(self.root)
  113.     def searchTree(self, k):
  114.         return self.search_tree_helper(self.root, k)
  116.     def minimum(self, node):
  117.         while node.left != self.TNULL:
  118.             node = node.left
  119.         return node
  121.     def maximum(self, node):
  122.         while node.right != self.TNULL:
  123.             node = node.right
  124.         return node
  126.     def successor(self, x):
  127.         if x.right != self.TNULL:
  128.             return self.minimum(x.right)
  130.         y = x.parent
  131.         while y != self.TNULL and x == y.right:
  132.             x = y
  133.             y = y.parent
  134.         return y
  136.     def predecessor(self,  x):
  137.         if (x.left != self.TNULL):
  138.             return self.maximum(x.left)
  140.         y = x.parent
  141.         while y != self.TNULL and x == y.left:
  142.             x = y
  143.             y = y.parent
  145.         return y
  147.     def left_rotate(self, x):
  148.         y = x.right
  149.         x.right = y.left
  150.         if y.left != self.TNULL:
  151.             y.left.parent = x
  153.         y.parent = x.parent
  154.         if x.parent == None:
  155.             self.root = y
  156.         elif x == x.parent.left:
  157.             x.parent.left = y
  158.         else:
  159.             x.parent.right = y
  160.         y.left = x
  161.         x.parent = y
  163.     def right_rotate(self, x):
  164.         y = x.left
  165.         x.left = y.right
  166.         if y.right != self.TNULL:
  167.             y.right.parent = x
  169.         y.parent = x.parent
  170.         if x.parent == None:
  171.             self.root = y
  172.         elif x == x.parent.right:
  173.             x.parent.right = y
  174.         else:
  175.             x.parent.left = y
  176.         y.right = x
  177.         x.parent = y
  179.     def insert(self, key):
  180.         node = Node(key)
  181.         node.parent = None
  182.         node.item = key
  183.         node.left = self.TNULL
  184.         node.right = self.TNULL
  185.         node.color = 1
  187.         y = None
  188.         x = self.root
  190.         while x != self.TNULL:
  191.             y = x
  192.             if node.item < x.item:
  193.                 x = x.left
  194.             else:
  195.                 x = x.right
  197.         node.parent = y
  198.         if y == None:
  199.             self.root = node
  200.         elif node.item < y.item:
  201.             y.left = node
  202.         else:
  203.             y.right = node
  205.         if node.parent == None:
  206.             node.color = 0
  207.             return
  209.         if node.parent.parent == None:
  210.             return
  212.         self.fix_insert(node)
  214.     def get_root(self):
  215.         return self.root
  217.     def print_tree(self):
  218.         self.__print_helper(self.root, "", True)
  220. if __name__ == "__main__":
  221.     bst = RedBlackTree()
  223.     bst.insert(55)
  224.     bst.insert(40)
  225.     bst.insert(65)
  226.     bst.insert(60)
  227.     bst.insert(75)
  228.     bst.insert(57)
  230.     bst.print_tree()
  1. // Implementing Red-Black Tree in Java
  3. class Node {
  4.   int data;
  5.   Node parent;
  6.   Node left;
  7.   Node right;
  8.   int color;
  9. }
  11. public class RedBlackTree {
  12.   private Node root;
  13.   private Node TNULL;
  15.   // Preorder
  16.   private void preOrderHelper(Node node) {
  17.     if (node != TNULL) {
  18.       System.out.print(node.data + " ");
  19.       preOrderHelper(node.left);
  20.       preOrderHelper(node.right);
  21.     }
  22.   }
  24.   // Inorder
  25.   private void inOrderHelper(Node node) {
  26.     if (node != TNULL) {
  27.       inOrderHelper(node.left);
  28.       System.out.print(node.data + " ");
  29.       inOrderHelper(node.right);
  30.     }
  31.   }
  33.   // Post order
  34.   private void postOrderHelper(Node node) {
  35.     if (node != TNULL) {
  36.       postOrderHelper(node.left);
  37.       postOrderHelper(node.right);
  38.       System.out.print(node.data + " ");
  39.     }
  40.   }
  42.   // Search the tree
  43.   private Node searchTreeHelper(Node node, int key) {
  44.     if (node == TNULL || key == node.data) {
  45.       return node;
  46.     }
  48.     if (key < node.data) {
  49.       return searchTreeHelper(node.left, key);
  50.     }
  51.     return searchTreeHelper(node.right, key);
  52.   }
  54.   // Balance the tree after deletion of a node
  55.   private void fixDelete(Node x) {
  56.     Node s;
  57.     while (x != root && x.color == 0) {
  58.       if (x == x.parent.left) {
  59.         s = x.parent.right;
  60.         if (s.color == 1) {
  61.           s.color = 0;
  62.           x.parent.color = 1;
  63.           leftRotate(x.parent);
  64.           s = x.parent.right;
  65.         }
  67.         if (s.left.color == 0 && s.right.color == 0) {
  68.           s.color = 1;
  69.           x = x.parent;
  70.         } else {
  71.           if (s.right.color == 0) {
  72.             s.left.color = 0;
  73.             s.color = 1;
  74.             rightRotate(s);
  75.             s = x.parent.right;
  76.           }
  78.           s.color = x.parent.color;
  79.           x.parent.color = 0;
  80.           s.right.color = 0;
  81.           leftRotate(x.parent);
  82.           x = root;
  83.         }
  84.       } else {
  85.         s = x.parent.left;
  86.         if (s.color == 1) {
  87.           s.color = 0;
  88.           x.parent.color = 1;
  89.           rightRotate(x.parent);
  90.           s = x.parent.left;
  91.         }
  93.         if (s.right.color == 0 && s.right.color == 0) {
  94.           s.color = 1;
  95.           x = x.parent;
  96.         } else {
  97.           if (s.left.color == 0) {
  98.             s.right.color = 0;
  99.             s.color = 1;
  100.             leftRotate(s);
  101.             s = x.parent.left;
  102.           }
  104.           s.color = x.parent.color;
  105.           x.parent.color = 0;
  106.           s.left.color = 0;
  107.           rightRotate(x.parent);
  108.           x = root;
  109.         }
  110.       }
  111.     }
  112.     x.color = 0;
  113.   }
  115.   private void rbTransplant(Node u, Node v) {
  116.     if (u.parent == null) {
  117.       root = v;
  118.     } else if (u == u.parent.left) {
  119.       u.parent.left = v;
  120.     } else {
  121.       u.parent.right = v;
  122.     }
  123.     v.parent = u.parent;
  124.   }
  126.   // Balance the node after insertion
  127.   private void fixInsert(Node k) {
  128.     Node u;
  129.     while (k.parent.color == 1) {
  130.       if (k.parent == k.parent.parent.right) {
  131.         u = k.parent.parent.left;
  132.         if (u.color == 1) {
  133.           u.color = 0;
  134.           k.parent.color = 0;
  135.           k.parent.parent.color = 1;
  136.           k = k.parent.parent;
  137.         } else {
  138.           if (k == k.parent.left) {
  139.             k = k.parent;
  140.             rightRotate(k);
  141.           }
  142.           k.parent.color = 0;
  143.           k.parent.parent.color = 1;
  144.           leftRotate(k.parent.parent);
  145.         }
  146.       } else {
  147.         u = k.parent.parent.right;
  149.         if (u.color == 1) {
  150.           u.color = 0;
  151.           k.parent.color = 0;
  152.           k.parent.parent.color = 1;
  153.           k = k.parent.parent;
  154.         } else {
  155.           if (k == k.parent.right) {
  156.             k = k.parent;
  157.             leftRotate(k);
  158.           }
  159.           k.parent.color = 0;
  160.           k.parent.parent.color = 1;
  161.           rightRotate(k.parent.parent);
  162.         }
  163.       }
  164.       if (k == root) {
  165.         break;
  166.       }
  167.     }
  168.     root.color = 0;
  169.   }
  171.   private void printHelper(Node root, String indent, boolean last) {
  172.     if (root != TNULL) {
  173.       System.out.print(indent);
  174.       if (last) {
  175.         System.out.print("R----");
  176.         indent += "   ";
  177.       } else {
  178.         System.out.print("L----");
  179.         indent += "|  ";
  180.       }
  182.       String sColor = root.color == 1 ? "RED" : "BLACK";
  183.       System.out.println(root.data + "(" + sColor + ")");
  184.       printHelper(root.left, indent, false);
  185.       printHelper(root.right, indent, true);
  186.     }
  187.   }
  189.   public RedBlackTree() {
  190.     TNULL = new Node();
  191.     TNULL.color = 0;
  192.     TNULL.left = null;
  193.     TNULL.right = null;
  194.     root = TNULL;
  195.   }
  197.   public void preorder() {
  198.     preOrderHelper(this.root);
  199.   }
  201.   public void inorder() {
  202.     inOrderHelper(this.root);
  203.   }
  205.   public void postorder() {
  206.     postOrderHelper(this.root);
  207.   }
  209.   public Node searchTree(int k) {
  210.     return searchTreeHelper(this.root, k);
  211.   }
  213.   public Node minimum(Node node) {
  214.     while (node.left != TNULL) {
  215.       node = node.left;
  216.     }
  217.     return node;
  218.   }
  220.   public Node maximum(Node node) {
  221.     while (node.right != TNULL) {
  222.       node = node.right;
  223.     }
  224.     return node;
  225.   }
  227.   public Node successor(Node x) {
  228.     if (x.right != TNULL) {
  229.       return minimum(x.right);
  230.     }
  232.     Node y = x.parent;
  233.     while (y != TNULL && x == y.right) {
  234.       x = y;
  235.       y = y.parent;
  236.     }
  237.     return y;
  238.   }
  240.   public Node predecessor(Node x) {
  241.     if (x.left != TNULL) {
  242.       return maximum(x.left);
  243.     }
  245.     Node y = x.parent;
  246.     while (y != TNULL && x == y.left) {
  247.       x = y;
  248.       y = y.parent;
  249.     }
  251.     return y;
  252.   }
  254.   public void leftRotate(Node x) {
  255.     Node y = x.right;
  256.     x.right = y.left;
  257.     if (y.left != TNULL) {
  258.       y.left.parent = x;
  259.     }
  260.     y.parent = x.parent;
  261.     if (x.parent == null) {
  262.       this.root = y;
  263.     } else if (x == x.parent.left) {
  264.       x.parent.left = y;
  265.     } else {
  266.       x.parent.right = y;
  267.     }
  268.     y.left = x;
  269.     x.parent = y;
  270.   }
  272.   public void rightRotate(Node x) {
  273.     Node y = x.left;
  274.     x.left = y.right;
  275.     if (y.right != TNULL) {
  276.       y.right.parent = x;
  277.     }
  278.     y.parent = x.parent;
  279.     if (x.parent == null) {
  280.       this.root = y;
  281.     } else if (x == x.parent.right) {
  282.       x.parent.right = y;
  283.     } else {
  284.       x.parent.left = y;
  285.     }
  286.     y.right = x;
  287.     x.parent = y;
  288.   }
  290.   public void insert(int key) {
  291.     Node node = new Node();
  292.     node.parent = null;
  293.     node.data = key;
  294.     node.left = TNULL;
  295.     node.right = TNULL;
  296.     node.color = 1;
  298.     Node y = null;
  299.     Node x = this.root;
  301.     while (x != TNULL) {
  302.       y = x;
  303.       if (node.data < x.data) {
  304.         x = x.left;
  305.       } else {
  306.         x = x.right;
  307.       }
  308.     }
  310.     node.parent = y;
  311.     if (y == null) {
  312.       root = node;
  313.     } else if (node.data < y.data) {
  314.       y.left = node;
  315.     } else {
  316.       y.right = node;
  317.     }
  319.     if (node.parent == null) {
  320.       node.color = 0;
  321.       return;
  322.     }
  324.     if (node.parent.parent == null) {
  325.       return;
  326.     }
  328.     fixInsert(node);
  329.   }
  331.   public Node getRoot() {
  332.     return this.root;
  333.   }
  335.   public void printTree() {
  336.     printHelper(this.root, "", true);
  337.   }
  339.   public static void main(String[] args) {
  340.     RedBlackTree bst = new RedBlackTree();
  341.     bst.insert(55);
  342.     bst.insert(40);
  343.     bst.insert(65);
  344.     bst.insert(60);
  345.     bst.insert(75);
  346.     bst.insert(57);
  347.     bst.printTree();
  349.   }
  350. }
// 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;
}

// 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();
}