[prev] [index] [next]

Red-Black Trees

Red-black trees are a representation of 2-3-4 trees using BST nodes.

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
Insertion algorithm: avoids worst case O(n) behaviour

Search algorithm: standard BST search