[Data Structure] Red-Black Tree - 1

A red-black tree is a BST with two node types, namely red and black, and supporting operations that ensure the tree is balanced when a node is inserted or removed. 

Rules:

• Every node is colored either red or black.
• The root node is black.
• A red node's children cannot be red. 
• A null child is considered to be a black leaf node.
• All paths from a node to any null leaf descendant node must have the same number of black nodes. 

 

These rules ensure that a tree with N nodes will have a height of O(log N).

 

After an insertion or removal of a node, the red-black tree can be unbalanced. 

Same as AVL trees, red-black trees use rotations to rebalance the tree. 

 

RBTreeRotateLeft(tree, node) {
   rightLeftChild = node⇢right⇢left
   if (node⇢parent != null)
      RBTreeReplaceChild(node⇢parent, node, node⇢right)
   else { // node is root
      tree⇢root = node⇢right
      tree⇢root⇢parent = null
   }
   RBTreeSetChild(node⇢right, "left", node)
   RBTreeSetChild(node, "right", rightLeftChild)
}