IMPLEMENTATION OF DYNAMIC PREFIX TRIES

Abstract

In this dissertation, Dynamic Prefix tries (DP-tries) are discussed and implemented. DP-tries are data structures with algorithms for insertion, deletion and retrieval to build and maintain a dynamic database of binary keys of arbitrary length. These data structures store binary keys which may be prefixes of each other. The retrieval time of the key is guaranteed to be at most linear in the length of the input key irrespective of trie size, even when searching for longest matching prefixes. DP-tries are very efficient, simple, non recursive and require minimum storage. Insertion and deletion operations have strictly local effects and their particular sequence is irrelevant for the structure of the resulting trie. The above mentioned data structure, alongwith its algorithms, has been implemented in C language, under UNIX environment. For the purpose of comparison, programs have also been developed for insertion and search in AVL trees and binary search trees.