Algorithms for generating and coding B-Trees.

Abstract

Gupta, Lee and Wong described algorithms for generating 2-3 trees and B-trees with a given number of nodes and left as open problems whether algorithms exist that generate them in lexicographic order, and whether it is possible to generate 2-3 trees (GLW) or B-Trees (GLW1) in constant average delay, exclusive of the output. In this thesis, we propose solutions to the open problems in both (GLW) and (GLW1). The main results of this thesis are: introducing a new notation of B-Trees which provides lexicographic order and a proof that (GLW) and (GLW1) algorithms do have a constant average delay (thus solving two open problems posed by Gupta, Lee and Wong). A new algorithm for generating 2-3 trees, with a given number of nodes, in lexicographic order is also presented. This algorithm is an improvement over (GLW) in terms of time complexity and storage. An algorithm for lexicographic generation of B-Trees with a given number of leaves is described. Finally new algorithms for coding and decoding B-Trees sequentially are described.