Drzewo o ograniczonym zrównoważeniu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Drzewo o ograniczonym zrównoważeniu, (Binary search tree of bounded balance, BB-drzewo, Weight balanced binary tree, wt-tree) to 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ść 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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • 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, pp 553--562, 1993

Linki zewnętrzne[edytuj | edytuj kod]