Radix Tree nodes

I've been working on an implementation of a radix tree (for strings/char arrays), but I'm having somewhat of a dilemma figuring out how to store what tree nodes are children of a particular tree nodes.

I've seen linked list implementations used in Trie's (somewhat similar to radix trees) and possibly some radix trees (it's been a while since I've last researched this topic), but that seems like it'd perform very poorly especially if you have a set of data which contains lots of common prefixes.

Now I'm wondering would using another data structure (e.g. a Binary Search Tree) be a better design choice? 开发者_开发技巧I think I can see a very substantial speed improvement over a simple linked list (O(log(n)) vs. O(n)) when there is data with a large number of common prefixes, but could there be some substantial compromises to performance elsewhere?

In particular I'm worried about cases where there aren't a large number of common prefixes, or any other possible obstacles which may cause one to choose a linked list over a binary search tree.

Alternatively, is there a better (i.e. faster/uses less memory) method for storing the children nodes?

You want to look for a kart-trie. A kart-trie uses a BST like data structure with a simple hash. You can find a description here: http://code.dogmap.org/kart.

You could use a trie in place of a BST or list. For BST you'll have to compute a hash which could be as expensive as traversing the trie (I'm thinking of a trie with an array of pointers to children, where you use a character as an index). You'll end up with a trie of tries. A better solution could be to build a trie, and then compress the links that aren't branching.