An optimal search tree: complete binary search tree

ABSTRACT

Definitions and properties of a complete binary tree and a binary search tree are well known [1]. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a tree a Complete Binary Search Tree, a CBS Tree for short. Two basic advantages of a CBS tree are that it is a search tree with minimum height and that it can be placed in an array. The latter allows for implementation of the data structure without the use of pointers.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 2: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978