A trie is a binary tree with it nodes has as many leafs as is suitable. A binary tree has only 2 leafs per nodes. In a trie it happens that a node doesn't contain any leafs. This happens over many nodes. This is considerable a waste of space. A radix-trie tries to eliminate this empty nodes by compressing them into 1 node. The difference between a radix-trie and suffix-trie is that a suffix-trie can solve text-based problems. A radix-trie is good to store a dictionnary and search for words. Or associative arrays. Or ip addresses.
Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. K=key n=string I have a written a kart-trie in php: https://sourceforge.net/projects/kart-trie The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. ----- Ursprüngliche Mitteilung ----- > @Chi: Would you please explain the process in a little bit more > details? It will be helpful. > Is Trie and Radix-Trie same? > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. To post to this group, send email to > algoge...@googlegroups.com. To unsubscribe from this group, send email > to algogeeks+unsubscr...@googlegroups.com. For more options, visit this > group at http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
