hey... what's about the storage managment ? the search text may not be a fixed length string.. is implementation of a node is fessible?
one alternative solution may be associate a hash table along with this. but again the problem with collision ,, to avoid collision u can use perfect hashing with universal hash function. you can also use an alternative solution hash function and priority queue using MAX heap... On Mon, Dec 27, 2010 at 2:20 AM, Chi <[email protected]> wrote: > 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 > > [email protected]. To unsubscribe from this group, send email > > to [email protected]. 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- DIPANKAR DUTTA M-TECH,Computer Science & Engg. E&C Dept,IIT ROORKEE Uttarakhand , India – 247667 ------------------------------------------- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:[email protected] <email%[email protected]> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
