Implementing a Dynamic Compressed Trie.
Stefan Nilsson, Matti J. Tikkanen · 1998
We present an order-preserving general purpose data structure for binary data, the LPC-trie. The structure is a highly compressed trie, using both level and path compression. The memory usage is similar to that of a balanced binary search tree, but the expected average depth is smaller. The LPC-trie is well suited to modern language environments with efficient memory allocation and garbage collection. We present an implementation in the Java programming language and show that the structure compares favorably to a balanced binary search tree. 1. Introduction We describe a dynamic main memory data structure for binary data, the level and path compressed trie or LPC-trie. The structure is a dynamic variant of a static level compressed trie or LC-trie [2]. The trie is a simple order preserving data structure supporting fast retrieval of elements and efficient nearest neighbor and range searches. There are several implementations of dynamic trie structures in the literature [5, 6, 8,...