No label defined (Q3322119)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3853098
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3853098 |
Statements
1982
0 references
search trees
0 references
optimality criterion
0 references
almost regular
0 references
0.8888911
0 references
0 references
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.
0 references