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.
A CHARACTERIZATION OF BINARY SEARCH NETWORKS / E. BARCUCCI; R. PINZANI; E. RODELLA; R. SPRUGNOLI. - STAMPA. - 529:(1991), pp. 126-135. (Intervento presentato al convegno FCT'91 tenutosi a Gosen (Germania)) [10.1007/3-540-54458-5_57].
A CHARACTERIZATION OF BINARY SEARCH NETWORKS
BARCUCCI, ELENA;PINZANI, RENZO;SPRUGNOLI, RENZO
1991
Abstract
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.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.