Talk:Radix tree

I'm deleting a couple of claims that predecessor/successor are O(1). Consider a radix tree with contents {0, 00, 000, ..., 0...0, 1}, where we have strings of 0's of length 1 through n. Then the straightforward predecessor algorithm would take O(n) time to find the predecessor of "1". (You could do it in O(1) if you also threaded a doubly-linked list through all your leaves, but the same could be said for any binary search tree.) If there's some clever algorithm I'm not thinking of, could you cite it (or at least describe the algorithm, possibly here on the Talk page) before reinstating these claims? Thanks, Cwitty 21:31, 7 October 2006 (UTC)

This counterexample applies to all dictionary data structures. For example, suppose you add n keys of length n to a hash table, and then do a lookup. Even after you've found the right hash bucket, you still need n operations to compare your key to the existing key. So it's O(n). Except it's not: hash table lookup is O(1). The mistake is to confound the key length and the number of elements. In typical practice key lengths are effectively constant; they don't dependent on the number of elements in your dictionary.

In a radix tree the obvious predecessor and successor algorithms take time proportional to the key length, but this is effectively constant, so they are O(1). Reilly 14:16, 14 November 2006 (UTC)

This page have many errors. One of the most prominant is that PATRICIA-trie is not a RADIX tree and it does not look the way it is described here. PATRICIA-tree uses loossy path-compression. See, e.g. the original paper of Morrison, the work Gwehenberger, where he describes a similar data-structure and the 3d Book of the Arts of Computer Programming. Moreover, the RADIX tree that is the main name of this entry is not widely-accepted computer term. Instead, it is a colloquialism that occurred in the mid-eighties.

Diagram

I have added a simple diagram (and I removed reqdiagram) . User:rocchini 2007-05-17