[prev] 56 [next]

Red-Black Trees

Definition of a red-black tree
  • a BST in which each node is marked red or black
  • no two red nodes appear consecutively on any path
  • a red node corresponds to a 2-3-4 sibling of its parent
  • a black node corresponds to a 2-3-4 child of its parent
    • if no parent (= root) → also black
Balanced red-black tree
  • all paths from root to leaf have same number of black nodes
Insertion algorithm: avoids worst case O(n) behaviour

Search algorithm: standard BST search