Search

A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered. Given a set I of identifiers, two methods are presented for building, in a mechanical way, perfect hashing functions, i.e. functions transforming the elements of I into unique addresses. The first method, the "quotient reduction" method, is shown to he complete in the sense that for every set I the smallest table in which the elements of! can be stored and from which they can be retrieved by using a perfect hashing function constructed by this method can be found. However, for nonuniformly distributed sets, this method can give rather sparse tables. The second method, the "remainder reduction" method, is not complete in the above sense, but it seems to give minimal (or almost minimal) tables for every kind of set. The two techniques are applicable directly to small sets. Some methods to extend these results to larger sets are also presented. A rough comparison with ordinary hashing is given which shows that this method can be used conveniently in several practical applications. [ABSTRACT FROM AUTHOR]

The problem of generating random, uniformly distributed, binary trees is considered. A closed formula that counts the number of trees having a left subtee with k-1 nodes (k=1,2,...,n) is found. By inverting the formula, random trees with n nodes are generated according to the appropriate probability distribution, determining the number of nodes in the left and right subtrees that can be generated recursively. The procedure is shown to run in time O(n), occupying an extra space in the order of O(√n)

Two paging techniques proposed by Muntz and Uzgalis to store a binary tree in secondary storage are considered. The first method (sequential allocation) is the basic allocation technique and here an exact formula is given, to be considered as a touchstone for every other method. Then a modification to the second method (grouped allocation) is proposed which gains control on storage utilization. This allows the structure to maintain both a high loading factor and a low retrieving time.

We investigate properties of binary (search) trees related to the “inorder” labelling of the nodes. Both permutation and uniform trees are considered. We give explicit formulas to count the number of interior, middle and final nodes (leaves) containing a specific label. Possible applications are discussed.