# Radix Tree Search

# Radix Tree Search

Radix tree search looks up a key in a compact prefix tree where edges store variable length substrings.

It is closely related to compressed tries. The main difference is that radix trees are typically implemented for byte sequences or strings and optimize memory layout and lookup performance.

## Problem

Given a radix tree `root` and a key `s`, determine whether `s` exists as a stored key.

Return true if present, otherwise false.

## Structure

Each node stores outgoing edges indexed by the first symbol of their label. Each edge contains:

| field   | meaning   |
| ------- | --------- |
| `label` | substring |
| `child` | next node |

Nodes also store a terminal flag indicating complete keys.

## Algorithm

Start at the root and consume the input string by matching edge labels.

```text id="rt0k2q"
radix_tree_search(root, s):
    node = root
    i = 0

    while i < length(s):
        c = s[i]

        if c not in node.edges:
            return false

        edge = node.edges[c]
        label = edge.label

        if s[i : i + length(label)] != label:
            return false

        i = i + length(label)
        node = edge.child

    return node.is_terminal
```

## Example

Stored keys:

| key    |
| ------ |
| "test" |
| "team" |
| "tea"  |

Possible radix tree:

```text id="rt1p9v"
(root)
  └─ "te"
      ├─ "st" (terminal)
      └─ "a" (terminal)
           └─ "m" (terminal)
```

Search for `"team"`:

| step | remaining | edge |
| ---- | --------- | ---- |
| 1    | team      | te   |
| 2    | am        | a    |
| 3    | m         | m    |

The final node is terminal, so the key exists.

Search for `"ten"` fails after matching `"te"` because no edge labeled `"n"` exists.

## Correctness

Each edge represents a sequence of characters that would appear consecutively in an uncompressed trie. Matching an edge label enforces exact agreement with stored prefixes.

If no matching edge exists for the next character, no stored key shares that prefix. If an edge label does not match the substring, the search diverges from all stored keys.

After consuming the full input, the terminal flag distinguishes a stored key from a prefix. Therefore the algorithm returns true exactly when the key exists.

## Complexity

Let $L$ be the length of the key.

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

The number of node transitions is typically smaller than in a standard trie because multiple characters are consumed per edge.

Space complexity:

$$
O(1)
$$

for iterative search.

## When to Use

Radix trees are useful when:

* keys are strings or byte sequences
* memory usage must be reduced compared to standard tries
* prefix queries and ordered traversal are required
* performance benefits from fewer node hops

They are commonly used in routing tables, dictionaries, and indexing systems.

## Implementation

```python id="rt2n8x"
class RadixEdge:
    def __init__(self, label, child):
        self.label = label
        self.child = child

class RadixNode:
    def __init__(self):
        self.edges = {}
        self.is_terminal = False

def radix_tree_search(root, s):
    node = root
    i = 0

    while i < len(s):
        c = s[i]

        if c not in node.edges:
            return False

        edge = node.edges[c]
        label = edge.label

        if not s.startswith(label, i):
            return False

        i += len(label)
        node = edge.child

    return node.is_terminal
```

```go id="rt3m6q"
type RadixEdge struct {
	Label string
	Child *RadixNode
}

type RadixNode struct {
	Edges      map[rune]*RadixEdge
	IsTerminal bool
}

func RadixTreeSearch(root *RadixNode, s string) bool {
	node := root
	runes := []rune(s)
	i := 0

	for i < len(runes) {
		c := runes[i]

		edge, ok := node.Edges[c]
		if !ok {
			return false
		}

		label := []rune(edge.Label)

		if i+len(label) > len(runes) {
			return false
		}

		for j := range label {
			if runes[i+j] != label[j] {
				return false
			}
		}

		i += len(label)
		node = edge.Child
	}

	return node.IsTerminal
}
```