A CHARACTERIZATION OF BINARY SEARCH NETWORKS

In this paper some properties of binary search networks are studied. The binary search networks constitute an extension of the binary search trees and, as a result, their performance depends on their size. This paper is particulary concerned with a subset of the binary search networks, called vertically convex binary search networks. We give a coded representation of them which allows us to determine the number, the average number of columns and the average right width of such binary search networks having a predetermined area. We also introduce two algorithms to calculate the height and left width of a vertically convex binary search network by means of a linear scanning of its codifying word.