scientific article; zbMATH DE number 3853098
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.
- scientific article; zbMATH DE number 1210933
- scientific article; zbMATH DE number 795222
- scientific article; zbMATH DE number 3914115
- Optimal Search in Trees
- scientific article; zbMATH DE number 1135820
- Optimal trees for functions of internal distance
- scientific article; zbMATH DE number 3891405
- On finding optimal polytrees
- Publication:5750392
- Optimal worst case trees
- Possibilistic search trees
- Optimal worst case trees
- Optimal factorizations of families of trees
- Searching in trees
- Some results on higher Suslin trees
- scientific article; zbMATH DE number 4135962 (Why is no real title available?)
- scientific article; zbMATH DE number 15993 (Why is no real title available?)
- scientific article; zbMATH DE number 1135820 (Why is no real title available?)
- The Optimization of Signed Trees
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)