Sprugnoli R. On local properties of binary trees. Internal note IEI-B77-06, 1977. |

Abstract (English) |
We introduce the concept of a "simple local property" of a binary (search) tree, as a property for which a "weight" can be attached to every node of the tree and this weight depends in a simple way on the weight of its father node. We give formulae to compute the average weight of any single node and the corresponding variance, with respect to all the trees with a predefined number of nodes. We show by examples that many useful properties of binary trees are simple local and therefore can be studied by means of our method. In particular, we give an exact formula for the sequential allocation of binary trees to secondary storage, as proposed by Muntz and Uzgalis. Finally, we propose an algorithm to improve the space-performance of the grouped allocation introduced by the same authors. This algorithm depends on the solution of what we call the "father problem" for a binary tree. This consists in finding the father of a node, when it has not been reached by the usual searching procedure for binary trees. We show that the father problem can be formulated as a property very similar to a simple local property and can be studied accordingly, .proving that the problem can be solved in a constant average number of accesses to nodes. | |

Subject | Binary trees Searching Data organization |

1) Download Document PDF |

Open access Restricted Private