Fast And Space Efficient Trie Searches

Searching and traversing m-way trees using tries is a well known and broadly used technique. Three algorithms are presented, two have constant insert, search and delete cost, are faster than Hash Trees and can be searched twice as quickly cas Ternary Search Trees (TST). The third has a lg(N) byte compare cost like a TST, but is faster. All require 60% less memory space per node than TST and, unlike Hash Trees, are smoothly extensible and support sorted order functions. The new algorithms defining Array Compacted Trees (ACT), Array Mapped Trees (AMT), Unary Search Trees (UST) and their variants are discussed. These new search trees are applicable in many diverse areas such as high performance IP routers, symbol tables, lexicon scanners and FSA state tables.