๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

New lower bounds on the cost of binary search trees

โœ Scribed by Roberte De Prisco; Alfredo De Santis

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
674 KB
Volume
156
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
โœ James Allen Fill ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 865 KB

We study the distribution Q on the set B, of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B,, when successive requests ar

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
โœ Luc Devroye; Carlos Zamora-Cura ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 256 KB ๐Ÿ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
โœ Katherine Heinrich; Guizhen Liu ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 286 KB ๐Ÿ‘ 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span