COMPSCI 61B Lecture Notes - Lecture 37: Radix, Glossary Of Ancient Roman Religion, Trie
1 Jun 2017
School
Department
Course
Professor
Document Summary
Tries will be roughly analogous to digit-by-digit radix sorting. Given a trie with n keys, and a key with l digits. Assume that the child can be found in constant time. In comparison, hashtable: theta(nl) worst case, theta(l) typical case, theta(l) best case. Like bsts, comparison is done digit-by-digit, allowing us to skip some characters. Hash tables may look at many unnecessary characters as the full hashcode needs to be computed. Like hash tables, searching is constant with respect to the number of keys. Theoretical asymptotic speed improvement is nice, but main appeal of tries is their ability to support rapid pre x matching and approximate matching. Finding all keys that match a given pre x. Somewhat counter-intuitive but easiest java representation of a trie does not store letters inside nodes, instead letter is stored implicitly on each link. For non smart-phone users, texting usually involves coopting your number buttons to type messages.
