# Red Black Tree Search

# 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

$$
node.key = x
$$

If no such node exists, return null.

## Algorithm

Traverse from the root using key comparisons.

```text id="n2k81x"
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

```id="k9d02p"
        8(B)
       /     \
    4(R)     12(R)
   /  \      /   \
 2(B) 6(B) 10(B) 14(B)
```

Search for `14`:

| step | node | comparison | move   |
| ---- | ---- | ---------- | ------ |
| 1    | 8    | 14 > 8     | right  |
| 2    | 12   | 14 > 12    | right  |
| 3    | 14   | equal      | return |

## 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

| case      | time        |
| --------- | ----------- |
| all cases | $O(\log n)$ |

Height bound:

$$
h \leq 2 \log_2(n + 1)
$$

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

```python id="w3k92m"
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
```

```go id="p81nzd"
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
}
```