Mr. Piccolo's New Writeupshttp://everything2.com/?node=New%20Writeups%20Atom%20Feed&foruser=Mr. Piccolo2003-04-22T18:07:36ZTrie (idea)http://m.everything2.com/user/Mr.+Piccolo/writeups/TrieMr. Piccolohttp://m.everything2.com/user/Mr.+Piccolo2003-04-22T18:07:36Z2003-04-22T18:07:36Z<p>Although a trie is most commonly useful for <a href="/title/dictionary">dictionaries</a> of words, you may desire a larger set of <a href="/title/character">character</a>s than just <a href="/title/26">26</a> <a href="/title/letter">letter</a>s. In such a case, expanding the code above to include <a href="/title/array">array</a>s of size <a href="/title/256">256</a> (to encompass the entire extended <a href="/title/ASCII+table">ASCII table</a>, for example) would be impractical, for <a href="/title/ram">memory</a> usage will go <a href="/title/really+big+thing">through the roof</a>--even for relatively small data sets. Converting that to a linked list would help minimize memory usage but could significanly increase <a href="/title/linear+search">search</a> times.</p>
<p>As an alternative to using an array or a <a href="/title/linked+list">linked list</a> to store each token in a given trie entry, some form of <a href="/title/abstract+data+type">tree</a> can be used instead (hint: an <a href="/title/avl+tree">avl tree</a> or a <a href="/title/binary+tree">binary tree</a>). Using an avl tree, for example, will reduce search times for a given token of an entry from <a href="/title/Big-oh+notation">O</a>(n) (using a linked list) to O(log n) as well as minimize memory usage over that of the array approach. As an additional bonus, dictionaries can be<!-- close unclosed tag --></p>…