Drzewo o ograniczonym zrównoważeniu

Drzewo o ograniczonym zrównoważeniu (ang. binary search tree of bounded balance, BB-drzewo, ang. weight balanced binary tree, wt-tree) – zrównoważone binarne drzewo poszukiwań (BST), w którym wielkość lewego i prawego poddrzewa każdego węzła jest nie większa niż o stały czynnik $w.$ Drzewa takie nie są w pełni zrównoważone (w porównaniu do drzew czerwono-czarnych czy drzew AVL). Warunek, iż jedno z poddrzew jest co najwyżej większe o czynnik $w$ jest równoważne stwierdzeniu, że jedno z poddrzew jest wyższe o stały czynnik. W praktyce takie drzewa są proste w implementacji i całkiem szybkie, gwarantując logarytmiczną złożoność wszystkich operacji, a tym samym zabezpieczając przed patologiczną sytuacją wysokiego niezrównoważenia. Drzewa te bywają również użyteczne przy implementacji operacji na zbiorach (takich jak suma, przecięcie – cześć wspólna, różnica, różnica wykluczająca itp.).

Drzewa te przywracają częściowe zrównoważenie przy pomocy pojedynczej lub podwójnej rotacji.

Drzewa te w każdym węźle przechowują czwórkę: klucz (z wartością), wskaźnik do lewego poddrzewa, wskaźnik do prawego poddrzewa oraz liczbę określającą rozmiar (ilość kluczy) drzewa.

Drzewa te są wyjątkowo dobre w przypadku implementacji w językach funkcyjnych, jako że w drzewach tych rzadko dokonuje się procedury wyważania, a w językach funkcyjnych procedura wyważania prowadziła do nowej alokacji pamięci z uwagi na to że raz stworzonych struktur danych nie można już zmienić (w przeciwieństwie do języków imperatywnych, gdzie można dokonać aktualizacji drzewa w miejscu).

Parametr $w,$ najczęściej posiada wartość większą niż 4.646, z uwagi na pewne teoretyczne właściwości rotacji na tych drzewach. W praktyce najmniejsza jego wartość to 5, co przekłada się na największą dopuszczalną różnicę pomiędzy wysokościami dowolnych poddrzew wynoszącą 3. Okazuje się jednak, że prowadzi to do błędnego zachowania algorytmu (przy operacji usuwania elementu mogą powstać drzewa które nie spełniają warunku zbalansowania). Jedynie pewne szczególne wartości gwarantują to zachowanie przy wszystkich możliwych scenariuszach dodawania i usuwania elementów. Szczegóły w referencjach.

Zobacz też

• drzewo czerwono-czarne

Bibliografia

• Adams S., Implementing sets efficiently in a functional language, „Technical Report CSTR” 92-10, University of Southampton, 1992.
• Adams S., Efficient sets: a balancing act, „Journal of Functional Programming”, Vol 3, No 4, s. 553–562, 1993.

Linki zewnętrzne

• Praca implementująca drzewo o ograniczonym zrównoważeniu w języku Standard ML wraz z dyskusją
• Binary search trees of bounded balance, J. Nievergelt, E. M. Reingold, Proceedings of the fourth annual ACM symposium on Theory of computing, p. 137–142, May 01-03, 1972, Denver, Colorado, United States
• Balancing Weight-Balanced Trees. hagi.is.s.u-tokyo.ac.jp. [zarchiwizowane z tego adresu (2012-03-15)]., „Journal of Functional Programming” vol. 21, issue 03, s. 287–307. (The old title is „Balance Condition on Weight-Balanced Trees”.)
• Weight-Balanced Trees Praca z 2011 roku, dowodząca jakie (całkowite) parametry algorytmy spełniają warunki poprawności (m.in. poprawne zrównoważenie drzewa). Równocześnie pokazuje to błąd w pracy Admsa z 1992, która była wykorzystywana w implementacji zbiorów w bibliotekach standardowych języka Haskell oraz Scheme (poprawione pod koniec 2010 roku).