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 Black.

Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "BB(α) tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bbalphatree.html