Red Black Tree Search

Red Black tree search uses the same traversal rule as a binary search tree, while relying on structural constraints enforced by node colors to keep the tree approximately balanced.

Each node is marked red or black, and the tree satisfies invariants that bound its height. This ensures predictable logarithmic search time without strict balancing.

Problem

Given a red black tree with root root and a target key x, find a node such that

If no such node exists, return null.

Algorithm

Traverse from the root using key comparisons.

rb_search(root, x):
    node = root
    while node != null:
        if x == node.key:
            return node
        else if x < node.key:
            node = node.left
        else:
            node = node.right
    return null

Example

        8(B)
       /     \
    4(R)     12(R)
   /  \      /   \
 2(B) 6(B) 10(B) 14(B)

Search for 14:

Correctness

The tree maintains the binary search ordering invariant. Therefore, each comparison correctly narrows the search to a single subtree.

Red black properties guarantee that no path is more than twice as long as any other path from root to leaf. This bounds the height.

Complexity

Height bound:

Space complexity:

• iterative: $O(1)$
• recursive: $O(\log n)$

When to Use

Red black tree search is suitable when:

• you need balanced performance with frequent updates
• insertions and deletions occur often
• strict balance is unnecessary but worst case guarantees are required

Compared to AVL trees, red black trees perform fewer rotations during updates, which improves insertion and deletion throughput.

Implementation

def rb_search(root, x):
    node = root
    while node:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right
    return None

func RBSearch(root *Node, x int) *Node {
    node := root
    for node != nil {
        if x == node.Key {
            return node
        } else if x < node.Key {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    return nil
}