NIST

BB(α) tree

(data structure)

Definition: A binary tree where the balance of every subtree, ρ(T'), is bounded by α ≤ ρ(T') ≤ 1-α.

Also known as weight-balanced tree.

Generalization (I am a kind of ...)
binary tree, balanced tree.

Specialization (... is a kind of me.)
D-tree.

See also height-balanced tree.

Note: After Johann Blieberger <blieb@auto.tuwien.ac.at>, Discrete Loops and Worst Case Performance, page 22.

See [GBY91, pages 100-102].

Author: PEB

Implementation

Worst-case behavior of traversal, annotated for real time (WOOP/ADA), including bibliography. insert (C and Pascal) and delete (C and Pascal) that use check root (C and Pascal) (or this one or this one?), left rotation (C and Pascal), and right rotation (C and Pascal).
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Fri Dec 30 16:00:23 2005.
HTML page formatted Fri Dec 30 16:00:32 2005.

Cite this as:
Paul E. Black, "BB(α) tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/bbalphatree.html

to NIST home page