# AVL Tree Search

# AVL Tree Search

AVL tree search follows the same decision process as binary search tree search, but operates on a tree that maintains strict height balance.

For every node, the height difference between left and right subtrees is at most one. This invariant ensures that the tree height remains logarithmic in the number of nodes.

## Problem

Given an AVL 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

The search logic matches standard BST search. The balancing property does not change the algorithm, only the height guarantee.

```text id="a1v8pq"
avl_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="z81kq2"
        8
       / \
      4   12
     / \  / \
    2  6 10 14
```

Search for `10`:

| step | node | comparison | move   |
| ---- | ---- | ---------- | ------ |
| 1    | 8    | 10 > 8     | right  |
| 2    | 12   | 10 < 12    | left   |
| 3    | 10   | equal      | return |

## Correctness

The AVL tree preserves the binary search tree ordering invariant. Therefore, at each step, the algorithm moves to the only subtree that can contain the target.

The balancing condition ensures that the search path length is bounded.

## Complexity

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

Height bound:

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

This guarantees logarithmic search time regardless of insertion order.

Space complexity:

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

## When to Use

AVL search is appropriate when:

* worst case performance must be guaranteed
* the dataset changes dynamically
* frequent lookups occur alongside insertions and deletions

Compared to red black trees, AVL trees provide faster lookups due to stricter balance, at the cost of more rotations during updates.

## Implementation

```python id="p0k9dw"
def avl_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="h7d3fa"
func AVLSearch(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
}
```