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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "BB(α) tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bbalphatree.html