Talk:Radix tree

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
???	This article has not yet received a rating on the assessment scale.
???	This article has not yet received an importance rating on the assessment scale.

[edit] 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 blatant is that PATRICIA-trie is not a RADIX tree and it does not look the way it is described here. PATRICIA-tree uses lossy 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.

[edit] Diagram

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