Red-Black Tree

Red-Black Tree

GFG

A red-black tree is a self-balancing binary search tree with useful properties for efficient lookups and updates.

Properties

  • Every node is either red or black
  • The root is always black
  • Every leaf (null) is black
  • If a node is red, then both children are black
  • the children of a red node are black. Hence possible parent of red node is a black node.
  • All paths from a node to leaves have the same number of black nodes

Red-Black Tree.excalidraw.svg

These properties ensure:

  • Balanced tree
  • O(log n) time for operations

Most of the BST operations (e.g., search, max, min, insert, delete.. etc.) take O(h) time where h is the height of the BST. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. 

Sr. No. Algorithm Time Complexity
1. Search O(log n)
2. Insert O(log n)
3. Delete O(log n)