# Patricia Trie Search

# Patricia Trie Search

Patricia trie search operates on a compressed binary trie where branching occurs only at bit positions that distinguish keys.

Instead of storing one level per bit, Patricia tries skip over uniform bit segments. Each node stores the bit index used for branching.

This structure is common for fixed width integer keys, IP routing, and compact prefix sets.

## Problem

Given a Patricia trie `root` and a key `x`, determine whether `x` exists in the trie.

Return true if present, otherwise false.

## Structure

Each node contains:

| field       | meaning                                        |
| ----------- | ---------------------------------------------- |
| `key`       | stored key (at leaves or representative nodes) |
| `bit_index` | bit position used for branching                |
| `left`      | child when bit is 0                            |
| `right`     | child when bit is 1                            |

The tree is organized so that each node compares a specific bit of the key.

## Algorithm

Start at the root and follow bit decisions. Stop when the next node does not advance in bit index. Then compare the stored key.

```text id="pt0k4q"
patricia_search(root, x):
    node = root
    prev = null

    while prev == null or node.bit_index > prev.bit_index:
        prev = node

        if bit(x, node.bit_index) == 0:
            node = node.left
        else:
            node = node.right

    if node.key == x:
        return true

    return false
```

## Example

Assume 4 bit keys:

| key | bits |
| --: | ---- |
|   3 | 0011 |
|   5 | 0101 |
|  12 | 1100 |

Search for `5`:

| step | node bit index | bit value | move               |
| ---- | -------------: | --------: | ------------------ |
| 1    |              1 |         1 | right              |
| 2    |              2 |         0 | left               |
| stop |              - |         - | compare stored key |

The final node contains key `5`, so the search succeeds.

## Correctness

Each node tests a bit position where stored keys differ. The traversal follows the same bit values as the target key, ensuring that only keys with matching prefixes remain possible.

The stopping condition detects when traversal cycles or stops progressing in bit index. At that point, the algorithm reaches a candidate node.

The final comparison verifies exact equality. If the stored key matches `x`, the key exists. Otherwise, no stored key has exactly the same bit pattern, so the key is absent.

## Complexity

Let $w$ be the number of bits in the key.

| operation | time   |
| --------- | ------ |
| search    | $O(w)$ |

Since $w$ is fixed for machine integers, search runs in constant time relative to the number of stored keys.

Space complexity:

$$
O(1)
$$

for iterative search.

## When to Use

Patricia tries are useful when:

* keys are fixed length integers or bit strings
* memory efficiency matters
* prefix matching or longest prefix queries are required
* routing tables or networking applications are involved

Compared to full tries, Patricia tries reduce node count significantly by compressing paths.

## Implementation

```python id="pt1q7z"
def bit(x, i):
    return (x >> i) & 1

class PatriciaNode:
    def __init__(self, key, bit_index):
        self.key = key
        self.bit_index = bit_index
        self.left = self
        self.right = self

def patricia_search(root, x):
    node = root
    prev = None

    while prev is None or node.bit_index > prev.bit_index:
        prev = node

        if bit(x, node.bit_index) == 0:
            node = node.left
        else:
            node = node.right

    return node.key == x
```

```go id="pt2m6v"
type PatriciaNode struct {
	Key      uint64
	BitIndex int
	Left     *PatriciaNode
	Right    *PatriciaNode
}

func bit(x uint64, i int) uint64 {
	return (x >> i) & 1
}

func PatriciaSearch(root *PatriciaNode, x uint64) bool {
	node := root
	var prev *PatriciaNode

	for prev == nil || node.BitIndex > prev.BitIndex {
		prev = node

		if bit(x, node.BitIndex) == 0 {
			node = node.Left
		} else {
			node = node.Right
		}
	}

	return node.Key == x
}
```