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

On rotations in fringe-balanced binary trees

โœ Scribed by Hosam M. Mahmoud

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
451 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We employ a P6lya urn to model rotations in a random fringe-balanced binary search tree. We show that asymptotically the number of rotations to construct a tree of size n has a normal distribution with mean +n and variance sn. Exact results for mean and variance are developed in the process. @ 1998 Published by Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

Embedding Large Complete Binary Trees in
Embedding Large Complete Binary Trees in Hypercubes with Load Balancing
โœ Kemal Efe ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 211 KB

In the next section we present basic definitions and notations where the criterion of optimality is defined and related to the concept of ''normal'' algorithms. In Section 3 we present an optimal embedding method that balances the processor loads. In Section 4 we present a nonoptimal embedding metho

On the joint distribution of the nodes i
On the joint distribution of the nodes in uniform multidimensional binary trees
โœ Rainer Kemp ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 313 KB ๐Ÿ‘ 2 views

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We d