Efficient Non-Sequential Access and More Ordering Choices in a Search Tree

Abstract—A traditional search tree allows for efficient sequen-tial access to the elements of the tree. In addition, a search tree allows for efficient insertion of new elements and efficient deletion of existing elements. In this article we show how to extend the capabilities of a search tree by presenting an algorithm for efficient access to predefined subsets of the indexed elements. This is achieved by marking some of the elements of the search tree with marker bits. In addition, our algorithm allows us to efficiently retrieve the indexed elements in either ascending or descending direction relative to each of the ordering attributes. Index Terms—marker bits; search trees; ordering directions; data structures I