Gewichtsbalancierte Suchbäume (oder BB-Bäume - bounded balance)
Zulässige Abweichung der Struktur vom ausgeglichenen
Binärbaum wird als Differenz zwischen der Anzahl der
Knoten im rechten und linken Unterbaum festgelegt.
Definition: Sei B ein binärer Suchbaum mit linkem Unterbaum Bl und l die Anzahl der Knoten in Bl (n sei entsprechend die Anzahl der Knoten in B)
(1) ? ( B ) = ( l + 1 ) / ( n + 1) heißt die Wurzelbalance von B.
(2) Ein Baum B heißt gewichtsbalanciert mit Balance ? (kurz ein BB (? )-Baum), wenn für jeden Unterbaum