Red-Black Tree

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(log n)	O(log n)	O(log n)	O(log n)

Definition

Short

Red-Black Tree is a type of self-balancing binary search tree that ensures the MAX height of any node is logarithmic and that no path from the root to any leaf node has more than a given number (usually 2) consecutive red nodes.

Simplified

Red-Black Tree is like a family tree with specific rules about the color of hats (red or black) each person wears. These rules ensure the tree remains balanced, which makes searching for a person (or data) efficient

Detailed

Red-Black Tree is a self-balancing binary search tree. Each node has an extra bit, interpreted as the color (red or black), which helps keep the tree balanced during insertions and deletions.

The tree is painted in a way that satisfies certain properties, ensuring it remains approximately balanced. When the tree is modified, it's rearranged and repainted to restore these properties.

While the balancing isn't perfect, it guarantees search, insertion, and deletion operations in O(log n) time.

A red-black tree must satisfy these conditions:

• Each node is either red or black
• The root is black
• All leaves (ø) are black
• If a node is red, its children are black
• Every path from a node to any of its descendant ø nodes contains the same number of black nodes

These constraints ensure that the path from the root to the farthest leaf is no more than twice as long as the path to the nearest leaf, making the tree roughly height-balanced. This allows red-black trees to be efficient in the worst case, unlike ordinary binary search trees.

Practice

Practice

Aspect	Pseudo Code
Insertion	insert_rbtree(tree, key): new_node = create_node(key) uncle = ø current_node = tree.root while current_node != ø: uncle = current_node if new_node.key < current_node.key: current_node = current_node.left_child else: current_node = current_node.right_child new_node.parent = uncle if uncle == ø: tree.root = new_node elif new_node.key < uncle.key: uncle.left_child = new_node else: uncle.right_child = new_node insert_fixup(tree, new_node) tree.root.color = BLACK # Ensure the root is always black create_node(key): node = new Node() node.key = key node.color = RED node.left_child = ø node.right_child = ø node.parent = ø return node left_rotate(tree, current_node): uncle = current_node.right_child current_node.right_child = uncle.left_child if uncle.left_child != ø: uncle.left_child.parent = current_node uncle.parent = current_node.parent if current_node.parent == ø: tree.root = uncle elif current_node == current_node.parent.left_child: current_node.parent.left_child = uncle else: current_node.parent.right_child = uncle uncle.left_child = current_node current_node.parent = uncle right_rotate(tree, uncle): current_node = uncle.left_child uncle.left_child = current_node.right_child if current_node.right_child != ø: current_node.right_child.parent = uncle current_node.parent = uncle.parent if uncle.parent == ø: tree.root = current_node elif uncle == uncle.parent.left_child: uncle.parent.left_child = current_node else: uncle.parent.right_child = current_node current_node.right_child = uncle uncle.parent = current_node insert_fixup(tree, new_node): while new_node.parent != ø and new_node.parent.color == RED: if new_node.parent == new_node.parent.parent.left_child: grand_parent_child = new_node.parent.parent.right_child if grand_parent_child != ø and grand_parent_child.color == RED: new_node.parent.color = BLACK grand_parent_child.color = BLACK new_node.parent.parent.color = RED new_node = new_node.parent.parent else: if new_node == new_node.parent.right_child: new_node = new_node.parent left_rotate(tree, new_node) new_node.parent.color = BLACK new_node.parent.parent.color = RED right_rotate(tree, new_node.parent.parent) else: grand_parent_child = new_node.parent.parent.left_child if grand_parent_child != ø and grand_parent_child.color == RED: new_node.parent.color = BLACK grand_parent_child.color = BLACK new_node.parent.parent.color = RED new_node = new_node.parent.parent else: if new_node == new_node.parent.left_child: new_node = new_node.parent right_rotate(tree, new_node) new_node.parent.color = BLACK new_node.parent.parent.color = RED left_rotate(tree, new_node.parent.parent)
Deletion	delete_rbtree(tree, key): node_to_delete = search(tree.root, key) if node_to_delete == ø: return successor = node_to_delete successor_original_color = successor.color if node_to_delete.left_child == ø: successor_child = node_to_delete.right_child transplant(tree, node_to_delete, node_to_delete.right_child) elif node_to_delete.right_child == ø: successor_child = node_to_delete.left_child transplant(tree, node_to_delete, node_to_delete.left_child) else: successor = find_min_node(node_to_delete.right_child) successor_original_color = successor.color successor_child = successor.right_child if successor.parent == node_to_delete: successor_child.parent = successor else: transplant(tree, successor, successor.right_child) successor.right_child = node_to_delete.right_child successor.right_child.parent = successor transplant(tree, node_to_delete, successor) successor.left_child = node_to_delete.left_child successor.left_child.parent = successor successor.color = node_to_delete.color if successor_original_color == BLACK: delete_fixup(tree, successor_child) search(root, key): current = root while current != ø and current.key != key: if key < current.key: current = current.left_child else: current = current.right_child return current find_min_node(node): while node.left_child != ø: node = node.left_child return node transplant(tree, parent, child): if parent.parent == ø: tree.root = child elif parent == parent.parent.left_child: parent.parent.left_child = child else: parent.parent.right_child = child if child != ø: child.parent = parent.parent delete_fixup(tree, current_node): while current_node != tree.root and (current_node == ø or current_node.color == BLACK): if current_node == current_node.parent.left_child: current_node_sibling = current_node.parent.right_child if current_node_sibling.color == RED: current_node_sibling.color = BLACK current_node.parent.color = RED left_rotate(tree, current_node.parent) current_node_sibling = current_node.parent.right_child if (current_node_sibling.left_child == ø or current_node_sibling.left_child.color == BLACK) and (current_node_sibling.right_child == ø or current_node_sibling.right_child.color == BLACK): current_node_sibling.color = RED current_node = current_node.parent else: if current_node_sibling.right_child == ø or current_node_sibling.right_child.color == BLACK: current_node_sibling.left_child.color = BLACK current_node_sibling.color = RED right_rotate(tree, current_node_sibling) current_node_sibling = current_node.parent.right_child current_node_sibling.color = current_node.parent.color current_node.parent.color = BLACK current_node_sibling.right_child.color = BLACK left_rotate(tree, current_node.parent) current_node = tree.root else: current_node_sibling = current_node.parent.left_child if current_node_sibling.color == RED: current_node_sibling.color = BLACK current_node.parent.color = RED right_rotate(tree, current_node.parent) current_node_sibling = current_node.parent.left_child if (current_node_sibling.right_child == ø or current_node_sibling.right_child.color == BLACK) and (current_node_sibling.left_child == ø or current_node_sibling.left_child.color == BLACK): current_node_sibling.color = RED current_node = current_node.parent else: if current_node_sibling.left_child == ø or current_node_sibling.left_child.color == BLACK: current_node_sibling.right_child.color = BLACK current_node_sibling.color = RED left_rotate(tree, current_node_sibling) current_node_sibling = current_node.parent.left_child current_node_sibling.color = current_node.parent.color current_node.parent.color = BLACK current_node_sibling.left_child.color = BLACK right_rotate(tree, current_node.parent) current_node = tree.root

Solution

package main

type Color string

const (
	RED   Color = "RED"
	BLACK Color = "BLACK"
)

type Node struct {
	Key        int
	Color      Color
	LeftChild  *Node
	RightChild *Node
	Parent     *Node
}

type RedBlackTree struct {
	Root *Node
}

func NewNode(key int, color Color, left, right, parent *Node) *Node {
	return &Node{
		Key:        key,
		Color:      color,
		LeftChild:  left,
		RightChild: right,
		Parent:     parent,
	}
}

func NewRedBlackTree() *RedBlackTree {
	return &RedBlackTree{}
}

func (tree *RedBlackTree) InsertRBTree(key int) {
	newNode := NewNode(key, RED, nil, nil, nil)
	var uncle *Node
	currentNode := tree.Root

	for currentNode != nil {
		uncle = currentNode
		if newNode.Key < currentNode.Key {
			currentNode = currentNode.LeftChild
		} else {
			currentNode = currentNode.RightChild
		}
	}

	newNode.Parent = uncle
	if uncle == nil {
		tree.Root = newNode
	} else if newNode.Key < uncle.Key {
		uncle.LeftChild = newNode
	} else {
		uncle.RightChild = newNode
	}

	tree.insertFixup(newNode)
	tree.Root.Color = BLACK
}

func (tree *RedBlackTree) leftRotate(currentNode *Node) {
	uncle := currentNode.RightChild
	currentNode.RightChild = uncle.LeftChild
	if uncle.LeftChild != nil {
		uncle.LeftChild.Parent = currentNode
	}
	uncle.Parent = currentNode.Parent

	if currentNode.Parent == nil {
		tree.Root = uncle
	} else if currentNode == currentNode.Parent.LeftChild {
		currentNode.Parent.LeftChild = uncle
	} else {
		currentNode.Parent.RightChild = uncle
	}

	uncle.LeftChild = currentNode
	currentNode.Parent = uncle
}

func (tree *RedBlackTree) rightRotate(uncle *Node) {
	currentNode := uncle.LeftChild
	uncle.LeftChild = currentNode.RightChild
	if currentNode.RightChild != nil {
		currentNode.RightChild.Parent = uncle
	}
	currentNode.Parent = uncle.Parent

	if uncle.Parent == nil {
		tree.Root = currentNode
	} else if uncle == uncle.Parent.LeftChild {
		uncle.Parent.LeftChild = currentNode
	} else {
		uncle.Parent.RightChild = currentNode
	}

	currentNode.RightChild = uncle
	uncle.Parent = currentNode
}

func (tree *RedBlackTree) insertFixup(newNode *Node) {
	current := newNode
	for current != nil && current.Parent != nil && current.Parent.Color == RED {
		if current.Parent == current.Parent.Parent.LeftChild {
			y := current.Parent.Parent.RightChild
			if y != nil && y.Color == RED {
				current.Parent.Color = BLACK
				y.Color = BLACK
				current.Parent.Parent.Color = RED
				current = current.Parent.Parent
			} else {
				if current == current.Parent.RightChild {
					current = current.Parent
					tree.leftRotate(current)
				}
				current.Parent.Color = BLACK
				current.Parent.Parent.Color = RED
				tree.rightRotate(current.Parent.Parent)
			}
		} else {
			y := current.Parent.Parent.LeftChild
			if y != nil && y.Color == RED {
				current.Parent.Color = BLACK
				y.Color = BLACK
				current.Parent.Parent.Color = RED
				current = current.Parent.Parent
			} else {
				if current == current.Parent.LeftChild {
					current = current.Parent
					tree.rightRotate(current)
				}
				current.Parent.Color = BLACK
				current.Parent.Parent.Color = RED
				tree.leftRotate(current.Parent.Parent)
			}
		}
	}
	tree.Root.Color = BLACK
}

func (tree *RedBlackTree) DeleteRBTree(key int) {
	nodeToDelete := tree.search(tree.Root, key)
	if nodeToDelete == nil {
		return
	}

	successor := nodeToDelete
	successorOriginalColor := successor.Color
	var successorChild *Node

	if nodeToDelete.LeftChild == nil {
		successorChild = nodeToDelete.RightChild
		tree.transplant(nodeToDelete, nodeToDelete.RightChild)
	} else if nodeToDelete.RightChild == nil {
		successorChild = nodeToDelete.LeftChild
		tree.transplant(nodeToDelete, nodeToDelete.LeftChild)
	} else {
		successor = tree.findMinNode(nodeToDelete.RightChild)
		successorOriginalColor = successor.Color
		successorChild = successor.RightChild

		if successor.Parent == nodeToDelete {
			if successorChild != nil {
				successorChild.Parent = successor
			}
		} else {
			tree.transplant(successor, successor.RightChild)
			successor.RightChild = nodeToDelete.RightChild
			if successor.RightChild != nil {
				successor.RightChild.Parent = successor
			}
		}

		tree.transplant(nodeToDelete, successor)
		successor.LeftChild = nodeToDelete.LeftChild
		if successor.LeftChild != nil {
			successor.LeftChild.Parent = successor
		}
		successor.Color = nodeToDelete.Color
	}

	if successorOriginalColor == BLACK {
		tree.deleteFixup(successorChild)
	}
}

func (tree *RedBlackTree) search(root *Node, key int) *Node {
	current := root
	for current != nil && current.Key != key {
		if key < current.Key {
			current = current.LeftChild
		} else {
			current = current.RightChild
		}
	}
	return current
}

func (tree *RedBlackTree) findMinNode(node *Node) *Node {
	current := node
	for current.LeftChild != nil {
		current = current.LeftChild
	}
	return current
}

func (tree *RedBlackTree) transplant(parent, child *Node) {
	if parent.Parent == nil {
		tree.Root = child
	} else if parent == parent.Parent.LeftChild {
		parent.Parent.LeftChild = child
	} else {
		parent.Parent.RightChild = child
	}

	if child != nil {
		child.Parent = parent.Parent
	}
}

func (tree *RedBlackTree) deleteFixup(currentNode *Node) {
	current := currentNode
	for current != tree.Root && (current == nil || current.Color == BLACK) {
		if current == current.Parent.LeftChild {
			currentSibling := current.Parent.RightChild
			if currentSibling != nil && currentSibling.Color == RED {
				currentSibling.Color = BLACK
				current.Parent.Color = RED
				tree.leftRotate(current.Parent)
				currentSibling = current.Parent.RightChild
			}
			if (currentSibling.LeftChild == nil || currentSibling.LeftChild.Color == BLACK) &&
				(currentSibling.RightChild == nil || currentSibling.RightChild.Color == BLACK) {
				currentSibling.Color = RED
				current = current.Parent
			} else {
				if currentSibling.RightChild == nil || currentSibling.RightChild.Color == BLACK {
					currentSibling.LeftChild.Color = BLACK
					currentSibling.Color = RED
					tree.rightRotate(currentSibling)
					currentSibling = current.Parent.RightChild
				}
				currentSibling.Color = current.Parent.Color
				current.Parent.Color = BLACK
				currentSibling.RightChild.Color = BLACK
				tree.leftRotate(current.Parent)

				current = tree.Root
			}
		} else {
			currentSibling := current.Parent.LeftChild
			if currentSibling != nil && currentSibling.Color == RED {
				currentSibling.Color = BLACK
				current.Parent.Color = RED
				tree.rightRotate(current.Parent)
				currentSibling = current.Parent.LeftChild
			}
			if (currentSibling.RightChild == nil || currentSibling.RightChild.Color == BLACK) &&
				(currentSibling.LeftChild == nil || currentSibling.LeftChild.Color == BLACK) {
				currentSibling.Color = RED
				current = current.Parent
			} else {
				if currentSibling.LeftChild == nil || currentSibling.LeftChild.Color == BLACK {
					currentSibling.RightChild.Color = BLACK
					currentSibling.Color = RED
					tree.leftRotate(currentSibling)
					currentSibling = current.Parent.LeftChild
				}
				currentSibling.Color = current.Parent.Color
				current.Parent.Color = BLACK
				currentSibling.LeftChild.Color = BLACK
				tree.rightRotate(current.Parent)

				current = tree.Root
			}
		}
	}
	if current != nil {
		current.Color = BLACK
	}
}

func inOrderTraversal(node *Node) {
	if node != nil {
		inOrderTraversal(node.LeftChild)
		fmt.Printf("Key: %d, Color: %s\n", node.Key, node.Color)
		inOrderTraversal(node.RightChild)
	}
}

public class RedBlackTree {

  enum Color {
    RED,
    BLACK
  }

  public static class Node {

    int key;
    String color;
    Node leftChild;
    Node rightChild;
    Node parent;

    public Node(int key, String color) {
      this.key = key;
      this.color = color;
    }
  }

  private Node root;

  public void insertRBTree(int key) {
    Node newNode = new Node(key, Color.RED.toString());
    Node uncle = null;
    Node currentNode = root;

    while (currentNode != null) {
      uncle = currentNode;
      if (newNode.key < currentNode.key) {
        currentNode = currentNode.leftChild;
      } else {
        currentNode = currentNode.rightChild;
      }
    }

    newNode.parent = uncle;
    if (uncle == null) {
      root = newNode;
    } else if (newNode.key < uncle.key) {
      uncle.leftChild = newNode;
    } else {
      uncle.rightChild = newNode;
    }

    insertFixup(newNode);
    root.color = Color.BLACK.toString();
  }

  private void leftRotate(Node currentNode) {
    Node uncle = currentNode.rightChild;
    currentNode.rightChild = uncle != null ? uncle.leftChild : null;
    if (uncle != null && uncle.leftChild != null) {
      uncle.leftChild.parent = currentNode;
    }
    if (uncle != null) {
      uncle.parent = currentNode.parent;
    }

    if (currentNode.parent == null) {
      root = uncle;
    } else if (currentNode == currentNode.parent.leftChild) {
      currentNode.parent.leftChild = uncle;
    } else {
      currentNode.parent.rightChild = uncle;
    }

    if (uncle != null) {
      uncle.leftChild = currentNode;
    }
    currentNode.parent = uncle;
  }

  private void rightRotate(Node uncle) {
    Node currentNode = uncle.leftChild;
    uncle.leftChild = currentNode != null ? currentNode.rightChild : null;
    if (currentNode != null && currentNode.rightChild != null) {
      currentNode.rightChild.parent = uncle;
    }
    if (currentNode != null) {
      currentNode.parent = uncle.parent;
    }

    if (uncle.parent == null) {
      root = currentNode;
    } else if (uncle == uncle.parent.leftChild) {
      uncle.parent.leftChild = currentNode;
    } else {
      uncle.parent.rightChild = currentNode;
    }

    if (currentNode != null) {
      currentNode.rightChild = uncle;
    }
    uncle.parent = currentNode;
  }

  private void insertFixup(Node newNode) {
    Node current = newNode;
    while (current != null && current.parent != null && current.parent.color.equals(Color.RED.toString())) {
      if (current.parent == current.parent.parent.leftChild) {
        Node y = current.parent.parent.rightChild;
        if (y != null && y.color.equals(Color.RED.toString())) {
          current.parent.color = Color.BLACK.toString();
          y.color = Color.BLACK.toString();
          current.parent.parent.color = Color.RED.toString();
          current = current.parent.parent;
        } else {
          if (current == current.parent.rightChild) {
            current = current.parent;
            leftRotate(current);
          }
          current.parent.color = Color.BLACK.toString();
          current.parent.parent.color = Color.RED.toString();
          rightRotate(current.parent.parent);
        }
      } else {
        Node y = current.parent.parent.leftChild;
        if (y != null && y.color.equals(Color.RED.toString())) {
          current.parent.color = Color.BLACK.toString();
          y.color = Color.BLACK.toString();
          current.parent.parent.color = Color.RED.toString();
          current = current.parent.parent;
        } else {
          if (current == current.parent.leftChild) {
            current = current.parent;
            rightRotate(current);
          }
          current.parent.color = Color.BLACK.toString();
          current.parent.parent.color = Color.RED.toString();
          leftRotate(current.parent.parent);
        }
      }
    }
    root.color = Color.BLACK.toString();
  }

  public void deleteRBTree(int key) {
    Node nodeToDelete = search(root, key);
    if (nodeToDelete == null) {
      return;
    }

    Node successor = nodeToDelete;
    String successorOriginalColor = successor.color;
    Node successorChild;

    if (nodeToDelete.leftChild == null) {
      successorChild = nodeToDelete.rightChild;
      transplant(nodeToDelete, nodeToDelete.rightChild);
    } else if (nodeToDelete.rightChild == null) {
      successorChild = nodeToDelete.leftChild;
      transplant(nodeToDelete, nodeToDelete.leftChild);
    } else {
      successor = findMinNode(nodeToDelete.rightChild);
      successorOriginalColor = successor.color;
      successorChild = successor.rightChild;

      if (successor.parent == nodeToDelete) {
        if (successorChild != null) {
          successorChild.parent = successor;
        }
      } else {
        transplant(successor, successor.rightChild);
        successor.rightChild = nodeToDelete.rightChild;
        if (successor.rightChild != null) {
          successor.rightChild.parent = successor;
        }
      }

      transplant(nodeToDelete, successor);
      successor.leftChild = nodeToDelete.leftChild;
      if (successor.leftChild != null) {
        successor.leftChild.parent = successor;
      }
      successor.color = nodeToDelete.color;
    }

    if (successorOriginalColor.equals(Color.BLACK.toString())) {
      deleteFixup(successorChild);
    }
  }

  private Node search(Node root, int key) {
    Node current = root;
    while (current != null && current.key != key) {
      while (current != null && current.key != key) {
        if (key < current.key) {
          current = current.leftChild;
        } else {
          current = current.rightChild;
        }
      }
      return current;
    }

    private Node findMinNode (Node node) {
      Node current = node;
      while (current.leftChild != null) {
        current = current.leftChild;
      }
      return current;
    }

    private void transplant (Node parent, Node child) {
      if (parent.parent == null) {
        root = child;
      } else if (parent == parent.parent.leftChild) {
        parent.parent.leftChild = child;
      } else {
        parent.parent.rightChild = child;
      }

      if (child != null) {
        child.parent = parent.parent;
      }
    }

    private void deleteFixup (Node currentNode) {
      Node current = currentNode;
      while (current != root && (current == null || current.color.equals(Color.BLACK.toString()))) {
        if (current == current.parent.leftChild) {
          Node currentSibling = current.parent.rightChild;
          if (currentSibling != null && currentSibling.color.equals(Color.RED.toString())) {
            currentSibling.color = Color.BLACK.toString();
            current.parent.color = Color.RED.toString();
            leftRotate(current.parent);
            currentSibling = current.parent.rightChild;
          }
          if ((currentSibling == null || currentSibling.leftChild == null || currentSibling.leftChild.color.equals(Color.BLACK.toString())) &&
              (currentSibling == null || currentSibling.rightChild == null || currentSibling.rightChild.color.equals(Color.BLACK.toString()))) {
            if (currentSibling != null) {
              currentSibling.color = Color.RED.toString();
            }
            current = current.parent;
          } else {
            if (currentSibling.rightChild == null || currentSibling.rightChild.color.equals(Color.BLACK.toString())) {
              if (currentSibling.leftChild != null) {
                currentSibling.leftChild.color = Color.BLACK.toString();
              }
              if (currentSibling != null) {
                currentSibling.color = Color.RED.toString();
              }
              rightRotate(currentSibling);
              currentSibling = current.parent.rightChild;
            }
            if (currentSibling != null) {
              currentSibling.color = current.parent.color;
            }
            if (current.parent != null) {
              current.parent.color = Color.BLACK.toString();
            }
            if (currentSibling.rightChild != null) {
              currentSibling.rightChild.color = Color.BLACK.toString();
            }
            leftRotate(current.parent);

            current = root;
          }
        } else {
          Node currentSibling = current.parent.leftChild;
          if (currentSibling != null && currentSibling.color.equals(Color.RED.toString())) {
            currentSibling.color = Color.BLACK.toString();
            current.parent.color = Color.RED.toString();
            rightRotate(current.parent);
            currentSibling = current.parent.leftChild;
          }
          if ((currentSibling == null || currentSibling.rightChild == null || currentSibling.rightChild.color.equals(Color.BLACK.toString())) &&
              (currentSibling == null || currentSibling.leftChild == null || currentSibling.leftChild.color.equals(Color.BLACK.toString()))) {
            if (currentSibling != null) {
              currentSibling.color = Color.RED.toString();
            }
            current = current.parent;
          } else {
            if (currentSibling.leftChild == null || currentSibling.leftChild.color.equals(Color.BLACK.toString())) {
              if (currentSibling.rightChild != null) {
                currentSibling.rightChild.color = Color.BLACK.toString();
              }
              if (currentSibling != null) {
                currentSibling.color = Color.RED.toString();
              }
              leftRotate(currentSibling);
              currentSibling = current.parent.leftChild;
            }
            if (currentSibling != null) {
              currentSibling.color = current.parent.color;
            }
            if (current.parent != null) {
              current.parent.color = Color.BLACK.toString();
            }
            if (currentSibling.leftChild != null) {
              currentSibling.leftChild.color = Color.BLACK.toString();
            }
            rightRotate(current.parent);
            current = root;
          }
        }
      }
      if (current != null) {
        current.color = Color.BLACK.toString();
      }
    }

    private static void inOrderTraversal (Node node) {
      if (node != null) {
        inOrderTraversal(node.leftChild);
        System.out.printf("Key: %d, Color: %s\n", node.key, node.color);
        inOrderTraversal(node.rightChild);
      }
    }
  }
}

class RedBlackTree {
    enum class Color {
        RED,
        BLACK
    }

    data class Node(var key: Int, var color: String, var leftChild: Node? = null, var rightChild: Node? = null, var parent: Node? = null)

    var root: Node? = null

    fun insertRBTree(key: Int) {
        val newNode = Node(key, RED)
        var uncle: Node? = null
        var currentNode = root

        while (currentNode != null) {
            uncle = currentNode
            if (newNode.key < currentNode.key) {
                currentNode = currentNode.leftChild
            } else {
                currentNode = currentNode.rightChild
            }
        }

        newNode.parent = uncle
        if (uncle == null) {
            root = newNode
        } else if (newNode.key < uncle.key) {
            uncle.leftChild = newNode
        } else {
            uncle.rightChild = newNode
        }

        insertFixup(newNode)
        root?.color = BLACK
    }

    private fun leftRotate(currentNode: Node) {
        val uncle = currentNode.rightChild
        currentNode.rightChild = uncle?.leftChild
        uncle?.leftChild?.parent = currentNode
        uncle?.parent = currentNode.parent

        if (currentNode.parent == null) {
            root = uncle
        } else if (currentNode == currentNode.parent?.leftChild) {
            currentNode.parent?.leftChild = uncle
        } else {
            currentNode.parent?.rightChild = uncle
        }

        uncle?.leftChild = currentNode
        currentNode.parent = uncle
    }

    private fun rightRotate(uncle: Node) {
        val currentNode = uncle.leftChild
        uncle.leftChild = currentNode?.rightChild
        currentNode?.rightChild?.parent = uncle
        currentNode?.parent = uncle.parent

        if (uncle.parent == null) {
            root = currentNode
        } else if (uncle == uncle.parent?.leftChild) {
            uncle.parent?.leftChild = currentNode
        } else {
            uncle.parent?.rightChild = currentNode
        }

        currentNode?.rightChild = uncle
        uncle.parent = currentNode
    }

    private fun insertFixup(newNode: Node?) {
        var current = newNode
        while (current?.parent != null && current.parent?.color == RED) {
            if (current.parent == current.parent?.parent?.leftChild) {
                val y = current.parent?.parent?.rightChild
                if (y != null && y.color == RED) {
                    current.parent?.color = BLACK
                    y.color = BLACK
                    current.parent?.parent?.color = RED
                    current = current.parent?.parent
                } else {
                    if (current == current.parent?.rightChild) {
                        current = current.parent
                        leftRotate(current)
                    }
                    current.parent?.color = BLACK
                    current.parent?.parent?.color = RED
                    rightRotate(current.parent?.parent!!)
                }
            } else {
                val y = current.parent?.parent?.leftChild
                if (y != null && y.color == RED) {
                    current.parent?.color = BLACK
                    y.color = BLACK
                    current.parent?.parent?.color = RED
                    current = current.parent?.parent
                } else {
                    if (current == current.parent?.leftChild) {
                        current = current.parent
                        rightRotate(current)
                    }
                    current.parent?.color = BLACK
                    current.parent?.parent?.color = RED
                    leftRotate(current.parent?.parent!!)
                }
            }
        }
        root?.color = BLACK
    }

    fun deleteRBTree(key: Int) {
        val nodeToDelete = search(root, key)
        if (nodeToDelete == null) {
            return
        }

        var successor = nodeToDelete
        var successorOriginalColor = successor.color
        val successorChild: Node?

        if (nodeToDelete.leftChild == null) {
            successorChild = nodeToDelete.rightChild
            transplant(nodeToDelete, nodeToDelete.rightChild)
        } else if (nodeToDelete.rightChild == null) {
            successorChild = nodeToDelete.leftChild
            transplant(nodeToDelete, nodeToDelete.leftChild)
        } else {
            successor = findMinNode(nodeToDelete.rightChild!!)
            successorOriginalColor = successor.color
            successorChild = successor.rightChild

            if (successor.parent == nodeToDelete) {
                successorChild?.parent = successor
            } else {
                transplant(successor, successor.rightChild)
                successor.rightChild = nodeToDelete.rightChild
                successor.rightChild?.parent = successor
            }

            transplant(nodeToDelete, successor)
            successor.leftChild = nodeToDelete.leftChild
            successor.leftChild?.parent = successor
            successor.color = nodeToDelete.color
        }

        if (successorOriginalColor == BLACK) {
            deleteFixup(successorChild)
        }
    }

    private fun search(root: Node?, key: Int): Node? {
        var current = root
        while (current != null && current.key != key) {
            if (key < current.key) {
                current = current.leftChild
            } else {
                current = current.rightChild
            }
        }
        return current
    }

    private fun findMinNode(node: Node): Node {
        var current = node
        while (current.leftChild != null) {
            current = current.leftChild!!
        }
        return current
    }

    private fun transplant(parent: Node, child: Node?) {
        if (parent.parent == null) {
            root = child
        } else if (parent == parent.parent?.leftChild) {
            parent.parent?.leftChild = child
        } else {
            parent.parent?.rightChild = child
        }

        child?.parent = parent.parent
    }

    private fun deleteFixup(currentNode: Node?) {
        var current = currentNode
        while (current != root && (current == null || current.color == BLACK)) {
            if (current == current?.parent?.leftChild) {
                var currentNodeSibling = current.parent?.rightChild
                if (currentNodeSibling?.color == RED) {
                    currentNodeSibling.color = BLACK
                    current.parent?.color = RED
                    leftRotate(current.parent!!)
                    currentNodeSibling = current.parent?.rightChild
                }
                if ((currentNodeSibling?.leftChild == null || currentNodeSibling.leftChild?.color == BLACK) &&
                        (currentNodeSibling.rightChild == null || currentNodeSibling.rightChild?.color == BLACK)
                ) {
                    currentNodeSibling.color = RED
                    current = current.parent
                } else {
                    if (currentNodeSibling.rightChild == null || currentNodeSibling.rightChild?.color == BLACK) {
                        currentNodeSibling.leftChild?.color = BLACK
                        currentNodeSibling.color = RED
                        rightRotate(currentNodeSibling)
                        currentNodeSibling = current.parent?.rightChild
                    }
                    currentNodeSibling?.color = current.parent?.color
                    current.parent?.color = BLACK
                    currentNodeSibling?.rightChild?.color = BLACK
                    leftRotate(tree, currentNode.parent!!)

                    current = root
                }
            } else {
                var currentNodeSibling = current.parent?.leftChild
                if (currentNodeSibling?.color == RED) {
                    currentNodeSibling.color = BLACK
                    current.parent?.color = RED
                    rightRotate(current.parent!!)
                    currentNodeSibling = current.parent?.leftChild
                }
                if ((currentNodeSibling?.rightChild == null || currentNodeSibling.rightChild?.color == BLACK) &&
                        (currentNodeSibling.leftChild == null || currentNodeSibling.leftChild?.color == BLACK)
                ) {
                    currentNodeSibling.color = RED
                    current = current.parent
                } else {
                    if (currentNodeSibling.leftChild == null || currentNodeSibling.leftChild?.color == BLACK) {
                        currentNodeSibling.rightChild?.color = BLACK
                        currentNodeSibling.color = RED
                        leftRotate(currentNodeSibling)
                        currentNodeSibling = current.parent?.leftChild
                    }
                    currentNodeSibling?.color = current.parent?.color
                    current.parent?.color = BLACK
                    currentNodeSibling?.leftChild?.color = BLACK
                    rightRotate(tree, currentNode.parent!!)
                    current = root
                }
            }
        }
        current?.color = BLACK
    }
}

class RedBlackTree:
    class Color:
        RED = "RED"
        BLACK = "BLACK"

    class Node:
        def __init__(self, key, color, left_child=None, right_child=None, parent=None):
            self.key = key
            self.color = color
            self.left_child = left_child
            self.right_child = right_child
            self.parent = parent

    def __init__(self):
        self.root = None

    def insert_rb_tree(self, key):
        new_node = self.Node(key, self.Color.RED)
        uncle = None
        current_node = self.root

        while current_node is not None:
            uncle = current_node
            if new_node.key < current_node.key:
                current_node = current_node.left_child
            else:
                current_node = current_node.right_child

        new_node.parent = uncle
        if uncle is None:
            self.root = new_node
        elif new_node.key < uncle.key:
            uncle.left_child = new_node
        else:
            uncle.right_child = new_node

        self._insert_fixup(new_node)
        if self.root is not None:
            self.root.color = self.Color.BLACK

    def _left_rotate(self, current_node):
        uncle = current_node.right_child
        current_node.right_child = uncle.left_child
        if uncle.left_child:
            uncle.left_child.parent = current_node
        uncle.parent = current_node.parent

        if current_node.parent is None:
            self.root = uncle
        elif current_node == current_node.parent.left_child:
            current_node.parent.left_child = uncle
        else:
            current_node.parent.right_child = uncle

        uncle.left_child = current_node
        current_node.parent = uncle

    def _right_rotate(self, uncle):
        current_node = uncle.left_child
        uncle.left_child = current_node.right_child
        if current_node.right_child:
            current_node.right_child.parent = uncle
        current_node.parent = uncle.parent

        if uncle.parent is None:
            self.root = current_node
        elif uncle == uncle.parent.left_child:
            uncle.parent.left_child = current_node
        else:
            uncle.parent.right_child = current_node

        current_node.right_child = uncle
        uncle.parent = current_node

    def _insert_fixup(self, new_node):
        current = new_node
        while current.parent is not None and current.parent.color == self.Color.RED:
            if current.parent == current.parent.parent.left_child:
                y = current.parent.parent.right_child
                if y and y.color == self.Color.RED:
                    current.parent.color = self.Color.BLACK
                    y.color = self.Color.BLACK
                    current.parent.parent.color = self.Color.RED
                    current = current.parent.parent
                else:
                    if current == current.parent.right_child:
                        current = current.parent
                        self._left_rotate(current)
                    current.parent.color = self.Color.BLACK
                    current.parent.parent.color = self.Color.RED
                    self._right_rotate(current.parent.parent)
            else:
                y = current.parent.parent.left_child
                if y and y.color == self.Color.RED:
                    current.parent.color = self.Color.BLACK
                    y.color = self.Color.BLACK
                    current.parent.parent.color = self.Color.RED
                    current = current.parent.parent
                else:
                    if current == current.parent.left_child:
                        current = current.parent
                        self._right_rotate(current)
                    current.parent.color = self.Color.BLACK
                    current.parent.parent.color = self.Color.RED
                    self._left_rotate(current.parent.parent)

        if self.root:
            self.root.color = self.Color.BLACK

    def delete_rb_tree(self, key):
        node_to_delete = self._search(self.root, key)
        if node_to_delete is None:
            return

        successor = node_to_delete
        successor_original_color = successor.color
        successor_child = None

        if node_to_delete.left_child is None:
            successor_child = node_to_delete.right_child
            self._transplant(node_to_delete, node_to_delete.right_child)
        elif node_to_delete.right_child is None:
            successor_child = node_to_delete.left_child
            self._transplant(node_to_delete, node_to_delete.left_child)
        else:
            successor = self._find_min_node(node_to_delete.right_child)
            successor_original_color = successor.color
            successor_child = successor.right_child

            if successor.parent == node_to_delete:
                if successor_child:
                    successor_child.parent = successor
            else:
                self._transplant(successor, successor.right_child)
                successor.right_child = node_to_delete.right_child
                if successor.right_child:
                    successor.right_child.parent = successor

            self._transplant(node_to_delete, successor)
            successor.left_child = node_to_delete.left_child
            if successor.left_child:
                successor.left_child.parent = successor
            successor.color = node_to_delete.color

        if successor_original_color == self.Color.BLACK:
            self._delete_fixup(successor_child)

    def _search(self, root, key):
        current = root
        while current and current.key != key:
            if key < current.key:
                current = current.left_child
            else:
                current = current.right_child
        return current

    def _find_min_node(self, node):
        current = node
        while current.left_child:
            current = current.left_child
        return current

    def _transplant(self, parent, child):
        if not parent.parent:
            self.root = child
        elif parent == parent.parent.left_child:
            parent.parent.left_child = child
        else:
            parent.parent.right_child = child

        if child:
            child.parent = parent.parent

    def _delete_fixup(self, current_node):
        current = current_node
        while current != self.root and (not current or current.color == self.Color.BLACK):
            if current == current.parent.left_child:
                current_sibling = current.parent.right_child
                if current_sibling and current_sibling.color == self.Color.RED:
                    current_sibling.color = self.Color.BLACK
                    current.parent.color = self.Color.RED
                    self._left_rotate(current.parent)
                    current_sibling = current.parent.right_child

                if (not current_sibling.left_child or current_sibling.left_child.color == self.Color.BLACK) and \
                        (not current_sibling.right_child or current_sibling.right_child.color == self.Color.BLACK):
                    if current_sibling:
                        current_sibling.color = self.Color.RED

                    current = current.parent
                else:
                    if not current_sibling.right_child or current_sibling.right_child.color == self.Color.BLACK:
                        if current_sibling.left_child:
                            current_sibling.left_child.color = self.Color.BLACK
                        if current_sibling:
                            current_sibling.color = self.Color.RED
                        self._right_rotate(current_sibling)
                        current_sibling = current.parent.right_child

                    if current_sibling:
                        current_sibling.color = current.parent.color
                    if current.parent:
                        current.parent.color = self.Color.BLACK
                    if current_sibling.right_child:
                        current_sibling.right_child.color = self.Color.BLACK

                    self._left_rotate(current.parent)
                    current = self.root
            else:
                current_sibling = current.parent.left_child
                if current_sibling and current_sibling.color == self.Color.RED:
                    current_sibling.color = self.Color.BLACK
                    current.parent.color = self.Color.RED
                    self._right_rotate(current.parent)
                    current_sibling = current.parent.left_child

                if (not current_sibling.right_child or current_sibling.right_child.color == self.Color.BLACK) and (not current_sibling.left_child or current_sibling.left_child.color == self.Color.BLACK):
                    if current_sibling:
                        current_sibling.color = self.Color.RED
                    current = current.parent
                else:
                    if not current_sibling.left_child or current_sibling.left_child.color == self.Color.BLACK:
                        if current_sibling.right_child:
                            current_sibling.right_child.color = self.Color.BLACK
                        if current_sibling:
                            current_sibling.color = self.Color.RED

                        self._left_rotate(current_sibling)
                        current_sibling = current.parent.left_child
                    if current_sibling:
                        current_sibling.color = current.parent.color
                    if current.parent:
                        current.parent.color = self.Color.BLACK
                    if current_sibling.left_child:
                        current_sibling.left_child.color = self.Color.BLACK

                    self._right_rotate(current.parent)
                    current = self.root
        if current:
            current.color = self.Color.BLACK

use std::cmp::Ord;

struct RedBlackTree {
    enum Color {
        RED,
        BLACK,
    }

    struct Node {
        key: i32,
        color: Color,
        left_child: Option<Box<Node>>,
        right_child: Option<Box<Node>>,
        parent: Option<Box<Node>>,
    }

    impl Node {
        fn new(key: i32, color: Color) -> Self {
            Node {
                key,
                color,
                left_child: None,
                right_child: None,
                parent: None,
            }
        }
    }

    impl RedBlackTree {
        root: Option<Box<Node>>,

        fn insert_rb_tree(&mut self, key: i32) {
            let new_node = Box::new(Node::new(key, Color::RED));
            let mut uncle: Option<Box<Node>> = None;
            let mut current_node = &mut self.root;

            while let Some(current) = current_node {
                uncle = Some(current);
                if new_node.key < current.key {
                    current_node = &mut current.left_child;
                } else {
                    current_node = &mut current.right_child;
                }
            }

            new_node.parent = uncle;
            if uncle.is_none() {
                self.root = Some(new_node);
            } else if new_node.key < uncle.unwrap().key {
                uncle.unwrap().left_child = Some(new_node);
            } else {
                uncle.unwrap().right_child = Some(new_node);
            }

            self.insert_fixup(Some(new_node));
            self.root.as_mut().map(|r| r.color = Color::BLACK);
        }

        fn left_rotate(&mut self, current_node: &mut Node) {
            let mut uncle = current_node.right_child.take();
            if let Some(ref mut uncle) = uncle {
                current_node.right_child = uncle.left_child.take();
                if let Some(left_child) = &mut uncle.left_child {
                    left_child.parent = Some(Box::new(current_node));
                }
                uncle.parent = current_node.parent.take();

                if current_node.parent.is_none() {
                    self.root = Some(uncle);
                } else if let Some(parent) = &mut current_node.parent {
                    if current_node.key < parent.key {
                        parent.left_child = Some(uncle);
                    } else {
                        parent.right_child = Some(uncle);
                    }
                }

                uncle.left_child = Some(Box::new(current_node));
                current_node.parent = Some(uncle);
            }
        }

        fn right_rotate(&mut self, uncle: &mut Node) {
            let mut current_node = uncle.left_child.take();
            if let Some(ref mut current_node) = current_node {
                uncle.left_child = current_node.right_child.take();
                if let Some(right_child) = &mut current_node.right_child {
                    right_child.parent = Some(Box::new(uncle));
                }
                current_node.parent = uncle.parent.take();

                if uncle.parent.is_none() {
                    self.root = current_node;
                } else if let Some(parent) = &mut uncle.parent {
                    if uncle.key < parent.key {
                        parent.left_child = current_node;
                    } else {
                        parent.right_child = current_node;
                    }
                }

                current_node.right_child = Some(Box::new(uncle));
                uncle.parent = current_node;
            }
        }

        fn insert_fixup(&mut self, new_node: Option<Box<Node>>) {
            let mut current = new_node;
            while let Some(ref mut current_node) = current {
                if let Some(ref parent) = current_node.parent {
                    if parent.color == Color::RED {
                        if parent == parent.parent.as_ref().and_then(|p| p.left_child.as_ref()) {
                            let y = parent.parent.as_ref().and_then(|p| p.right_child.as_ref());
                            if let Some(y) = y {
                                if y.color == Color::RED {
                                    parent.color = Color::BLACK;
                                    y.color = Color::BLACK;
                                    parent.parent.as_mut().map(|p| p.color = Color::RED);
                                    current = parent.parent;
                                } else {
                                    if current_node == parent.right_child.as_ref().and_then(|p| Some(p)) {
                                        current = Some(Box::new(parent));
                                        self.left_rotate(current_node);
                                    }
                                    parent.color = Color::BLACK;
                                    parent.parent.as_mut().map(|p| p.color = Color::RED);
                                    self.right_rotate(parent.parent.as_mut().and_then(|p| Some(p)).unwrap());
                                }
                            }
                        } else {
                            let y = parent.parent.as_ref().and_then(|p| p.left_child.as_ref());
                            if let Some(y) = y {
                                if y.color == Color::RED {
                                    parent.color = Color::BLACK;
                                    y.color = Color::BLACK;
                                    parent.parent.as_mut().map(|p| p.color = Color::RED);
                                    current = parent.parent;
                                } else {
                                    if current_node == parent.left_child.as_ref().and_then(|p| Some(p)) {
                                        current = Some(Box::new(parent));
                                        self.right_rotate(current_node);
                                    }
                                    parent.color = Color::BLACK;
                                    parent.parent.as_mut().map(|p| p.color = Color::RED);
                                    self.left_rotate(parent.parent.as_mut().and_then(|p| Some(p)).unwrap());
                                }
                            }
                        }
                    }
                }
            }
        }

        fn delete_rb_tree(&mut self, key: i32) {
            let node_to_delete = self.search(&self.root, key);
            if node_to_delete.is_none() {
                return;
            }

            let mut successor = node_to_delete.unwrap();
            let successor_original_color = successor.color;
            let mut successor_child: Option<Box<Node>>;

            if successor.left_child.is_none() {
                successor_child = successor.right_child.take();
                self.transplant(&successor, successor.right_child.as_mut());
            } else if successor.right_child.is_none() {
                successor_child = successor.left_child.take();
                self.transplant(&successor, successor.left_child.as_mut());
            } else {
                let min_node = self.find_min_node(successor.right_child.as_ref().and_then(|r| Some(r)));
                successor_original_color = min_node.color;
                successor_child = min_node.right_child.take();

                if let Some(ref parent) = min_node.parent {
                    if min_node.parent == &successor {
                        successor_child.as_mut().map(|child| child.parent = Some(Box::new(min_node)));
                    } else {
                        self.transplant(min_node.as_ref().and_then(|m| Some(m)), min_node.right_child.as_mut());
                        min_node.right_child = successor.right_child.take();
                        min_node.right_child.as_mut().map(|right| right.parent = Some(Box::new(min_node)));
                    }
                    self.transplant(&successor, Some(Box::new(min_node)));
                    min_node.left_child = successor.left_child.take();
                    min_node.left_child.as_mut().map(|left| left.parent = Some(Box::new(min_node)));
                    min_node.color = successor.color;
                }

                if successor_original_color == Color::BLACK {
                    self.delete_fixup(&successor_child);
                }
            }
        }

        fn search(&self, root: &Option<Box<Node>>, key: i32) -> Option<Box<Node>> {
            let mut current = root;
            while let Some(node) = current {
                if key < node.key {
                   current = &node.left_child;
               } else if key > node.key {
                   current = &node.right_child;
               } else {
                   return Some(Box::new(node.clone()));
               }
           }
           None
       }

       fn find_min_node(&self, mut node: Option<&Box<Node>>) -> &Box<Node> {
           while let Some(n) = node {
               node = n.left_child.as_ref();
           }
           node.unwrap()
       }

       fn transplant(&mut self, parent: &Node, child: Option<&mut Box<Node>>) {
           if parent.parent.is_none() {
               self.root = child.map(|c| c.clone());
           } else if let Some(parent_ref) = parent.parent.as_mut() {
               if parent == parent_ref.left_child.as_ref().map(|left| left.as_ref()) {
                   parent_ref.left_child = child.map(|c| c.clone());
               } else {
                   parent_ref.right_child = child.map(|c| c.clone());
               }
           }

           child.map(|c| c.parent = parent.parent.clone());
       }

       fn delete_fixup(&mut self, mut current_node: &Option<Box<Node>>) {
           while let Some(ref mut current) = *current_node {
               if current == &self.root.unwrap() {
                   break;
               }

               let mut current_sibling = current.parent.as_ref().and_then(|p| {
                   if current == p.left_child.as_ref().map(|left| left.as_ref()) {
                       p.right_child.as_ref().map(|right| right.as_ref())
                   } else {
                       p.left_child.as_ref().map(|left| left.as_ref())
                   }
               });

               if let Some(ref mut sibling) = current_sibling {
                   if sibling.color == Color::RED {
                       sibling.color = Color::BLACK;
                       current.parent.as_mut().map(|p| p.color = Color::RED);

                       if current == current.parent.as_ref().and_then(|p| p.left_child.as_ref().map(|left| left.as_ref())) {
                           self.left_rotate(current.parent.as_mut().unwrap());
                           current_sibling = current.parent.as_ref().and_then(|p| p.right_child.as_ref().map(|right| right.as_ref()));
                       } else {
                           self.right_rotate(current.parent.as_mut().unwrap());
                           current_sibling = current.parent.as_ref().and_then(|p| p.left_child.as_ref().map(|left| left.as_ref()));
                       }
                   }

                   if let (Some(ref left_child), Some(ref right_child)) =
                       (sibling.left_child.as_ref(), sibling.right_child.as_ref())
                   {
                       if left_child.color == Color::BLACK && right_child.color == Color::BLACK {
                           sibling.color = Color::RED;
                           current_node = &current.parent;
                       } else {
                           if current == current.parent.as_ref().and_then(|p| p.left_child.as_ref().map(|left| left.as_ref())) &&
                               right_child.color == Color::BLACK
                           {
                               left_child.color = Color::BLACK;
                               sibling.color = Color::RED;
                               self.right_rotate(sibling.as_mut().unwrap());
                               current_sibling = current.parent.as_ref().and_then(|p| p.right_child.as_ref().map(|right| right.as_ref()));
                           } else if current == current.parent.as_ref().and_then(|p| p.right_child.as_ref().map(|right| right.as_ref())) &&
                               left_child.color == Color::BLACK
                           {
                               right_child.color = Color::BLACK;
                               sibling.color = Color::RED;
                               self.left_rotate(sibling.as_mut().unwrap());
                               current_sibling = current.parent.as_ref().and_then(|p| p.left_child.as_ref().map(|left| left.as_ref()));
                           }

                           if let Some(ref mut sibling) = current_sibling {
                               sibling.color = current.parent.as_ref().map(|p| p.color).unwrap();
                               current.parent.as_mut().map(|p| p.color = Color::BLACK);
                               if current == current.parent.as_ref().and_then(|p| p.left_child.as_ref().map(|left| left.as_ref())) {
                                   right_child.color = Color::BLACK;
                                   self.left_rotate(current.parent.as_mut().unwrap());
                               } else {
                                   left_child.color = Color::BLACK;
                                   self.right_rotate(current.parent.as_mut().unwrap());
                               }
                           }

                           current_node = &self.root;
                       }
                   }
               }
           }

           if let Some(ref mut current) = *current_node {
               current.color = Color::BLACK;
           }
       }
   }
}

class RedBlackTree {
  enum Color {
    RED,
    BLACK
  }

  class Node {
    key: number;
    color: string;
    leftChild: Node | null;
    rightChild: Node | null;
    parent: Node | null;

    constructor(key: number, color: string, leftChild: Node | null = null, rightChild: Node | null = null, parent: Node | null = null) {
      this.key = key;
      this.color = color;
      this.leftChild = leftChild;
      this.rightChild = rightChild;
      this.parent = parent;
    }
  }

  root: Node | null = null;

  insertRBTree(key: number): void {
    const newNode = new Node(key, Color.RED);
    let uncle: Node | null = null;
  let currentNode: Node | null = this.root;

  while (currentNode !== null) {
    uncle = currentNode;
    if (newNode.key < currentNode.key) {
      currentNode = currentNode.leftChild;
    } else {
      currentNode = currentNode.rightChild;
    }
  }

  newNode.parent = uncle;
  if (uncle === null) {
    this.root = newNode;
  } else if (newNode.key < uncle.key) {
    uncle.leftChild = newNode;
  } else {
    uncle.rightChild = newNode;
  }

  this.insertFixup(newNode);
  if (this.root !== null) {
    this.root.color = Color.BLACK;
  }
  }

  private leftRotate(currentNode: Node): void {
    const uncle = currentNode.rightChild;
    if (uncle !== null) {
    currentNode.rightChild = uncle.leftChild;
    if (uncle.leftChild !== null) {
      uncle.leftChild.parent = currentNode;
    }
    uncle.parent = currentNode.parent;

    if (currentNode.parent === null) {
      this.root = uncle;
    } else if (currentNode === currentNode.parent.leftChild) {
      currentNode.parent.leftChild = uncle;
    } else {
      currentNode.parent.rightChild = uncle;
    }

    uncle.leftChild = currentNode;
    currentNode.parent = uncle;
  }
  }

  private rightRotate(uncle: Node): void {
    const currentNode = uncle.leftChild;
    if (currentNode !== null) {
    uncle.leftChild = currentNode.rightChild;
    if (currentNode.rightChild !== null) {
      currentNode.rightChild.parent = uncle;
    }
    currentNode.parent = uncle.parent;

    if (uncle.parent === null) {
      this.root = currentNode;
    } else if (uncle === uncle.parent.leftChild) {
      uncle.parent.leftChild = currentNode;
    } else {
      uncle.parent.rightChild = currentNode;
    }

    currentNode.rightChild = uncle;
    uncle.parent = currentNode;
  }
  }

  private insertFixup(newNode: Node | null): void {
    let current = newNode;
    while (current?.parent !== null && current.parent.color === Color.RED) {
    if (current.parent === current.parent.parent?.leftChild) {
      const y = current.parent.parent?.rightChild;
      if (y !== null && y.color === Color.RED) {
        current.parent.color = Color.BLACK;
        y.color = Color.BLACK;
        if (current.parent.parent !== null) {
          current.parent.parent.color = Color.RED;
        }
        current = current.parent.parent;
      } else {
        if (current === current.parent.rightChild) {
          current = current.parent;
          this.leftRotate(current);
        }
        if (current.parent !== null) {
          current.parent.color = Color.BLACK;
        }
        if (current.parent?.parent !== null) {
          current.parent.parent.color = Color.RED;
          this.rightRotate(current.parent.parent);
        }
      }
    } else {
      const y = current.parent.parent?.leftChild;
      if (y !== null && y.color === Color.RED) {
        current.parent.color = Color.BLACK;
        y.color = Color.BLACK;
        if (current.parent.parent !== null) {
          current.parent.parent.color = Color.RED;
        }
        current = current.parent.parent;
      } else {
        if (current === current.parent.leftChild) {
          current = current.parent;
          this.rightRotate(current);
        }
        if (current.parent !== null) {
          current.parent.color = Color.BLACK;
        }
        if (current.parent?.parent !== null) {
          current.parent.parent.color = Color.RED;
          this.leftRotate(current.parent.parent);
        }
      }
    }
  }
  if (this.root !== null) {
    this.root.color = Color.BLACK;
  }
  }

  deleteRBTree(key: number): void {
    const nodeToDelete = this.search(this.root, key);
    if (nodeToDelete === null) {
    return;
  }

  let successor = nodeToDelete;
  let successorOriginalColor = successor.color;
  let successorChild: Node | null;

  if (nodeToDelete.leftChild === null) {
    successorChild = nodeToDelete.rightChild;
    this.transplant(nodeToDelete, nodeToDelete.rightChild);
  } else if (nodeToDelete.rightChild === null) {
    successorChild = nodeToDelete.leftChild;
    this.transplant(nodeToDelete, nodeToDelete.leftChild);
  } else {
    successor = this.findMinNode(nodeToDelete.rightChild);
    successorOriginalColor = successor.color;
    successorChild = successor.rightChild;

    if (successor.parent === nodeToDelete) {
      if (successorChild !== null) {
        successorChild.parent = successor;
      }
    } else {
      this.transplant(successor, successor.rightChild);
      if (successor.rightChild !== null) {
        successor.rightChild.parent = successor;
      }
      successor.rightChild = nodeToDelete.rightChild;
      if (successor.rightChild !== null) {
        successor.rightChild.parent = successor;
      }
    }

    this.transplant(nodeToDelete, successor);
    successor.leftChild = nodeToDelete.leftChild;
    if (successor.leftChild !== null) {
      successor.leftChild.parent = successor;
    }
    successor.color = nodeToDelete.color;
  }

  if (successorOriginalColor === Color.BLACK) {
    this.deleteFixup(successorChild);
  }
  }

  private search(root: Node | null, key: number): Node | null {
    let current = root;
    while (current !== null && current.key !== key) {
      if (key < current.key) {
        current = current.leftChild;
      } else {
        current = current.rightChild;
      }
    }
    return current;
  }

  private findMinNode(node: Node): Node {
    let current = node;
    while (current.leftChild !== null) {
      current = current.leftChild;
    }
    return current;
  }

  private transplant(parent: Node, child: Node | null): void {
    if (parent.parent === null) {
    this.root = child;
  } else if (parent === parent.parent.leftChild) {
    parent.parent.leftChild = child;
  } else {
    parent.parent.rightChild = child;
  }

  if (child !== null) {
    child.parent = parent.parent;
  }
  }

  private deleteFixup(currentNode: Node | null): void {
    let current = currentNode;
    while (current !== this.root && (current === null || current.color === Color.BLACK)) {
      if (current === current?.parent?.leftChild) {
        let currentNodeSibling = current.parent?.rightChild;
        if (currentNodeSibling?.color === Color.RED) {
          currentNodeSibling.color = Color.BLACK;
          if (current.parent !== null) {
            current.parent.color = Color.RED;
          }
          if (current.parent !== null) {
            this.leftRotate(current.parent);
          }
          currentNodeSibling = current.parent?.rightChild;
        }
        if (
            (currentNodeSibling?.leftChild === null || currentNodeSibling.leftChild.color === Color.BLACK) &&
            (currentNodeSibling.rightChild === null || currentNodeSibling.rightChild.color === Color.BLACK)
        ) {
          if (currentNodeSibling !== null) {
            currentNodeSibling.color = Color.RED;
          }
          current = current.parent;
        } else {
          if (currentNodeSibling?.rightChild === null || currentNodeSibling.rightChild.color === Color.BLACK) {
            if (currentNodeSibling?.leftChild !== null) {
              currentNodeSibling.leftChild.color = Color.BLACK;
            }
            if (currentNodeSibling !== null) {
              currentNodeSibling.color = Color.RED;
            }
            if (current.parent !== null) {
              this.rightRotate(current.parent);
            }
            currentNodeSibling = current.parent?.rightChild;
          }
          if (currentNodeSibling !== null) {
            currentNodeSibling.color = current.parent?.color || Color.BLACK;
          }
          if (current.parent !== null) {
            current.parent.color = Color.BLACK;
          }
          if (currentNodeSibling?.rightChild !== null) {
            currentNodeSibling.rightChild.color = Color.BLACK;
          }
          if (current.parent !== null) {
            this.leftRotate(current.parent);
          }
          current = this.root;
        }
      } else {
        let currentNodeSibling = current.parent?.leftChild;
        if (currentNodeSibling?.color === Color.RED) {
          currentNodeSibling.color = Color.BLACK;
          if (current.parent !== null) {
            current.parent.color = Color.RED;
          }
          if (current.parent !== null) {
            this.rightRotate(current.parent);
          }
          currentNodeSibling = current.parent?.leftChild;
        }
        if (
            (currentNodeSibling?.rightChild === null || currentNodeSibling.rightChild.color === Color.BLACK) &&
            (currentNodeSibling.leftChild === null || currentNodeSibling.leftChild.color === Color.BLACK)
        ) {
          if (currentNodeSibling !== null) {
            currentNodeSibling.color = Color.RED;
          }
          current = current.parent;
        } else {
          if (currentNodeSibling?.leftChild === null || currentNodeSibling.leftChild.color === Color.BLACK) {
            if (currentNodeSibling?.rightChild !== null) {
              currentNodeSibling.rightChild.color = Color.BLACK;
            }
            if (currentNodeSibling !== null) {
              currentNodeSibling.color = Color.RED;
            }
            if (current.parent !== null) {
              this.leftRotate(current.parent);
            }
            currentNodeSibling = current.parent?.leftChild;
          }
          if (currentNodeSibling !== null) {
            currentNodeSibling.color = current.parent?.color || Color.BLACK;
          }
          if (current.parent !== null) {
            current.parent.color = Color.BLACK;
          }
          if (currentNodeSibling?.leftChild !== null) {
            currentNodeSibling.leftChild.color = Color.BLACK;
          }
          if (current.parent !== null) {
            this.rightRotate(current.parent);
          }
          current = this.root;
        }
    }
  }
  if (current !== null) {
    current.color = Color.BLACK;
  }
  }
}