Problem 12-2 Radix trees

Answer

A radix tree has the following invariants:

1.     L being the set of keys  in the left subtree of F and R being the set of keys in the right subtree of F we have for all F:  ∀ x∈L ∀ y∈R x < y

2.      For all F we have that parent(F) < F

The fist and second invariant holds because of the fist and second 

part of the definition  for lexicographically less than respectively.

Also because of transitivity we know that each key is less than all its descendants.

So knowing this 2 invariant we know we can do a pre-order walk. 

But is pre-oder walk Θ(n)? 

We know that for a tree of x nodes pre-order  walk runs in  Θ(x).

 The key of a node is like a trail to get were he is and each bit is a turn.

In each turn there is a node  but the paths may partially overlap for each key. 

Knowing this we can say that x - 1  ≤ n  and therefore the runtime is  Θ(n)