Fast and Space Efficient Trie Searches Phil Bagwell ACM 计算机科学

Fast And Space Efficient Trie SearchesPhil BagwellSearching and traversing m-way trees using tries is a well known and broadly used technique. Three algorithms are presented, two have constant insert, search or delete cost, are faster than Hash Trees and can be searched twice as quickly as Ternary Search Trees (TST). The third has a lgN 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 sor