Thank u for reading. My kart-trie is between a radix-trie and suffix-trie because a radix-trie can also have as many leafs as suitable and a suffix-trie also. A kart-trie has exactly 2 leafs per node.
Correct me if I'm wrong! ----- Ursprüngliche Mitteilung ----- > 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. > -- 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.
