Red-Black Tree

A self-balancing binary search tree with color properties that ensure the tree remains approximately balanced. Guarantees logarithmic time operations.

Red-Black Tree Visualization

SlowFast
🔊 Sound
ReadyEmpty Red-Black Tree. Insert a value.
Red NodeBlack Node● Search path● FoundEdge → red childEdge → black child
empty tree — insert a value

Complexity

Time Complexity: O(log n)
Space Complexity: O(n)

Pseudocode

function insert(root, key):
  node = standard BST insert
  color node red
  while node != root and node.parent is red:
    if parent is left child:
      uncle = parent.parent.right
      if uncle is red:
        recolor parent, uncle, grandparent
        node = grandparent
      else:
        if node is right child:
          node = parent
          rotateLeft(node)
        recolor parent and grandparent
        rotateRight(grandparent)
    else:
      (mirror case)
  color root black

Related Algorithms

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left subtree contains values less than the node, while the right subtree contains values greater than the node.

Time: O(log n) average, O(n) worst for search/insert/delete | Space: O(n)

AVL Tree

A self-balancing binary search tree where the difference between heights of left and right subtrees is at most one. Ensures fast lookups, insertions, and deletions.

Time: O(log n) | Space: O(n)