Strona główna▸Algorytmy i SI▸Treap — losowo zrównoważone drzewo BST

🎲 Treap — losowo zrównoważone drzewo BST

Każdy klucz w trepie (treap) otrzymuje losowy priorytet; drzewo pozostaje kopcem maksymalnym względem priorytetów, będąc jednocześnie drzewem BST względem kluczy, co daje oczekiwaną złożoność O(log n) bez jawnych reguł balansowania.

Algorytmy i SI2DZaawansowany60 FPS

O symulacji Treap — losowo zrównoważone drzewo BST

Treap to losowe drzewo poszukiwań binarnych, które łączy drzewo BST z kopcem — stąd nazwa — wprowadzone przez Cecilię Aragon i Raimunda Seidela w 1989 roku. Każdy węzeł przechowuje klucz oraz niezależnie wylosowany priorytet. Klucze spełniają niezmiennik drzewa poszukiwań binarnych, a priorytety jednocześnie spełniają niezmiennik kopca maksymalnego: priorytet każdego węzła jest nie mniejszy niż priorytety jego dzieci. Ponieważ priorytety są losowe, powstały kształt drzewa jest rozkładowo równoważny drzewu BST zbudowanemu poprzez wstawianie kluczy w losowej kolejności, co gwarantuje oczekiwaną wysokość O(log n) bez deterministycznych reguł balansowania. Wstawianie wykonuje zwykłe wstawianie BST według klucza, przypisuje losowy priorytet, a następnie obraca nowy węzeł w górę, dopóki narusza on właściwość kopca względem rodzica. Usuwanie obraca docelowy węzeł w dół, w stronę tego dziecka, które ma wyższy priorytet, aż do momentu, gdy można go usunąć. W przeciwieństwie do drzew AVL czy czerwono-czarnych, które wymuszają równowagę poprzez jawne niezmienniki, treap osiąga równowagę probabilistycznie, a dodatkowo obsługuje operacje podziału i scalania w czasie O(log n) dla zbiorów uporządkowanych.

Najczęściej zadawane pytania

Dlaczego losowe priorytety dają trepowi oczekiwaną wysokość O(log n)?

Ponieważ priorytet każdego węzła jest wybierany niezależnie i jednostajnie losowo, drzewo powstałe z uporządkowania węzłów według priorytetu ma taki sam rozkład jak drzewo BST zbudowane przez wstawianie kluczy w losowej permutacji. Losowe drzewa BST to klasyczny wynik z oczekiwaną wysokością O(log n), więc treap dziedziczy tę gwarancję bez konieczności jawnego rebalansowania.

Jak działa obrót podczas wstawiania?

Nowy klucz jest najpierw umieszczany za pomocą zwykłego rekurencyjnego wstawiania BST, stając się liściem z nowym losowym priorytetem. Jeśli ten priorytet przewyższa priorytet rodzica, węzeł jest obracany w górę — obrót w prawo, jeśli jest lewym dzieckiem, obrót w lewo, jeśli jest prawym dzieckiem. Obroty trwają, aż priorytet rodzica będzie większy lub węzeł stanie się korzeniem.

Jak usuwanie „obraca węzeł w dół”?

Aby usunąć węzeł z dwoma dziećmi, algorytm obraca w górę to dziecko, które ma wyższy priorytet, co przesuwa docelowy węzeł w dół, do przeciwnego poddrzewa, zachowując przy tym właściwość kopca maksymalnego. Powtarza się to, aż węzeł będzie miał co najwyżej jedno dziecko — wtedy jest bezpośrednio usuwany z drzewa.

Dlaczego treapy nie wymagają jawnych niezmienników równowagi, jak drzewa AVL czy czerwono-czarne?

Drzewa AVL i czerwono-czarne śledzą wysokość lub bity koloru dla każdego węzła i po każdej aktualizacji stosują deterministyczne, zależne od przypadku reguły rebalansowania. Treap zamiast tego polega na losowych priorytetach: ponieważ kształt zależy wyłącznie od liczb losowych, oczekiwana wysokość pozostaje logarytmiczna automatycznie, bez potrzeby prowadzenia ewidencji i bez przypadków rebalansowania wymagających dowodu poprawności.

⚙ Pod maską

binary search treerandomized algorithmbalanced treedata structure

2D · HTML5 Canvas 2D · cel 60 FPS · działa w całości po stronie klienta, bez instalacji