Height, Size Performance of Complete and Nearly Complete Binary Search Trees in Dictionary Applications

摘要

Trees are frequently used data structures for fast access to the stored data. Data structures like arrays, vectors and linked lists are limited by the trade-off between the ability to perform a fast search and the ability to resize easily. Binary Search Trees are an alternative data structure that is both dynamic in size and easily searchable. Now-a-days, more and more people are getting interested in using electronic organizers and telephone dictionaries avoiding the hard copy counter parts. In this paper, performance of complete and nearly complete binary search trees are analyzed in terms of the number of tree nodes and the tree heights. Analytical results are used together with an electronic telephone dictionary for a medium sized organization. It's performance is evaluated in lieu of the real-world applications. The concept of multiple keys in data structure literature is relatively new, and was first introduced by the author. To determine the dictionary performance, another algorithm for determining the internal and the external path lengths is also discussed. New results on performance analysis are presented. Using tree-sort, individual records inside the dictionary may be displayed in ascending order.