scientific article; zbMATH DE number 3853098

From MaRDI portal
Publication:3322119





The author considers search trees as used for storage and access of data. Instead of considering special types of regular trees, like binary or ternary trees, the shape of the tree is left free to adjust to an optimality criterion with respect to the time required for a probe. The central conjecture is that optimal trees are almost regular in the sense that all nodes sufficiently distant from the leaves have the same number of sons. The cost of a probe into a tree T is \(\sum_{v}f\) (number of sons), where v ranges over the nodes on the path of T which is probed. The cost of a tree T is the cost of the most expensive path from the root to a leaf of T. The author derives two results: 1. If f increases faster than the logarithmic function then the number of sons of a node in an optimal tree is bounded by a constant. 2. If \(f(x)=x^ m\), \(m>2\), then optimal trees are almost binary.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3322119)