# Weight Balanced Tree Search

# Weight Balanced Tree Search

Weight balanced tree search uses the ordinary binary search tree search rule, but the tree shape is maintained by subtree size constraints.

Each node stores or can derive the size of its subtree. Insertions and deletions use these sizes to detect imbalance and restore balance with rotations. Search itself only follows key comparisons.

## Problem

Given a weight balanced 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

At each node, compare the target key with the current key. Move left if the target is smaller, move right if the target is larger, and return when the keys match.

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

```text id="t3xb9p"
        12
       /  \
      6    18
     / \   / \
    3   9 15 21
```

Search for `15`:

| step | node | comparison | move   |
| ---- | ---: | ---------- | ------ |
| 1    |   12 | 15 > 12    | right  |
| 2    |   18 | 15 < 18    | left   |
| 3    |   15 | equal      | return |

## Correctness

A weight balanced tree preserves the binary search tree ordering invariant. For any node, every key in the left subtree is smaller than the node key, and every key in the right subtree is larger.

The algorithm moves into exactly the subtree that can contain the target. If it returns a node, that node has key `x`. If it reaches null, no node on the unique valid search path contains `x`, so the target does not occur in the tree.

## Complexity

Because subtree sizes are kept balanced, the tree height is logarithmic.

| case                                 | time        |
| ------------------------------------ | ----------- |
| worst case, under maintained balance | $O(\log n)$ |

Space complexity:

| version   | space       |
| --------- | ----------- |
| iterative | $O(1)$      |
| recursive | $O(\log n)$ |

## When to Use

Weight balanced trees are useful when each node already stores subtree size, or when order statistics are needed together with search.

They are appropriate when:

* search, insertion, and deletion must stay logarithmic
* rank and select operations are also useful
* subtree sizes are already part of the data structure

Compared with AVL trees, weight balanced trees use size balance rather than height balance.

## Implementation

```python id="z1k8fp"
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.size = 1

def weight_balanced_search(root, x):
    node = root

    while node is not None:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right

    return None
```

```go id="e8x2md"
type WeightBalancedNode struct {
	Key   int
	Left  *WeightBalancedNode
	Right *WeightBalancedNode
	Size  int
}

func WeightBalancedSearch(root *WeightBalancedNode, x int) *WeightBalancedNode {
	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
}
```