Treap: Drzewo BST równoważne stworzone z rzutu monetą

Problem z prostym drzewem BST

Drzewo binarne wyszukiwania jest szybkie tylko wtedy, gdy jest prawie równoważne. Wstawiając klucze w uporządkowanej kolejności, drzewo binarne wyszukiwania staje się de facto listą skierowaną — wysokość n, każda operacja O(n). Drzewa AVL i czerwono-czarne naprawiają to za pomocą zasad obracania aktywowanych przez jasno zdefiniowany invariant równowagi, co działa, ale analiza przypadkowa dla wstawiania i usuwania jest znanej jako bardzo skomplikowana. Treap (drzewo + koperta) osiąga oczekiwany czas O(log n) wysokości za pomocą mucha prostszej idei: każdemu kluczowi przypisuje się liczbę losową, a ta liczba wykonuje równowagę.

Dwa porządkowania, przeprowadzane jednocześnie

Każdy węzeł przechowuje klucz i priorytet wylosowany jednorodnie losowo podczas insertowania. Drzewo sprawia, że obie właściwości są spełnione jednocześnie:

Porządek BST: przetwarzanie w porządku in-order odwiedza klucze w uporządkowanej kolejności Priorytet drzewa kopcowego: każdy priorytet węzła >= priorytet obu jego dzieci Dla dowolnego zestawu par (klucz, priorytet) z unikalnymi wartościami istnieje dokładnie jedno kształt drzewa spełniające oba ograniczenia — więc struktura jest całkowicie wyznaczona w chwili wyboru priorytetów, niezależnie od kolejności przybywania kluczy.

BST order:   in-order traversal visits keys in sorted order
Heap order:  every node's priority >= both children's priorities

Wstawianie za pomocą obrótów

Wstawianie jak w zwykłym drzewie BST — idziemy w dół porównując klucze aż do znalezienia pustego miejsca — następnie przywracamy porządek kopcowy, obracając nowy węzeł w górę ponad dowolnym rodzicem o mniejszym priorytecie, dokładnie jak sift-up w kopcu binarnym, ale używając obrót drzewa zamiast zamian w tablicy:

function rotateRight(y) {          // y becomes right child of x
  const x = y.left;
  y.left = x.right;
  x.right = y;
  return x;                        // x is the new subtree root
}
// insert(node), then while node.priority > node.parent.priority:
//   rotate right or left depending on which child node is

Dlaczego losowe priorytety gwarantują oczekiwany czas O(log n) wysokości

To jest rezultat udowodniony przez Raimunda Seidela i Cecilię Aragon w 1996 roku: drzewo treap stworzone z dowolnej sekwencji wstawiania kluczy, przy warunku że priorytety są losowane niezależnie, ma dokładnie taką samą rozkład prawdopodobieństwa kształtów jak proste drzewo BST stworzone przez wstawianie tych samych kluczy w losowej i równomiernie rozłożonej kolejności. Nie ma znaczenia, czy rzeczywista kolejność wstawiania była uporządkowana, odwrotnie uporządkowana lub wybrana wrogie — same priorytety decydują o kształcie, a proste drzewo BST w losowej i równomiernie rozłożonej kolejności jest znane zawsze mieć oczekiwany czas wysokości O(log n). Drzewo treap dostaje za darmo gwarancję przypadkowej kolejności wstawiania dla średniego przypadku, na dowolnym wejściu.

Podział i scalanie: operacje, które sprawiają, że drzewa treap są specjalne

split(t, key) dzieli drzewo treap na dwa drzewa — wszystko mniejsze od klucza, wszystko większe — w czasie O(log n), przechodząc po drzewie raz i ponownie łącząc poddrzewa podczas przeprowadzania się. merge(t1, t2) jest odwrotnością tej operacji: dana są dwie drzewa treap, w których każdy klucz z t1 jest mniejszy niż każdy klucz z t2; te drzewa łączą się w jedno, ponownie w czasie O(log n), za pomocą zawsze łączenia korzenia o wyższej priorytetowości i rekursji na drugiej stronie:

function merge(t1, t2) { if (!t1) return t2; if (!t2) return t1; if (t1.priority > t2.priority) { t1.right = merge(t1.right, t2); return t1; } else { t2.left = merge(t1, t2.left); return t2; } } Ponieważ operacje podziału i scalania są tak mechaniczne, drzewo treap niejawne — w którym „klucz” to po prostu pozycja elementu w sekwencji zamiast przechowywanej wartości — obsługuje operacje, które są bolesne w większości innych równoważnych drzew: wyjmowanie kontynuowanego zakresu, odwracanie go i splicing powrotem na innym miejscu, wszystko w czasie O(log n). To dlatego drzewa treap pojawiają się jako osłona dla edytorsów tekstu podobnych do liny i struktur tablicowych wymagających odwrócenia zakresu lub przesunięcia.

function merge(t1, t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  if (t1.priority > t2.priority) {
    t1.right = merge(t1.right, t2);
    return t1;
  } else {
    t2.left = merge(t1, t2.left);
    return t2;
  }
}

Treap vs AVL vs red-black

Drzewa AVL i czerwono-czarne gwarantują O(log n) wysokość w najgorszym przypadku, nie używając żadnej losowości — przeciwnik widzący każdą operację nigdy nie może zmusić do złej wydajności. Treap tylko gwarantuje O(log n) oczekiwanej wartości; możliwe jest run z terriblicznym szczęściem w priorytetach losowych, ale to bardzo niemożliwe i niezauważalne dla przeciwnika nieznanego zaszyfrowanego seeda. W zamian treap ma kod znacznie prostszy — bez bitów koloru, bez czynników równowagi, bez logiki rotacji wielokrotnej dla usuwania — a komponuje się: podział i połączenie pozwalają budować operacje zakresu, utrwałość i statystyki porządkowe z kilkoma dodatkowymi linijkami kodu zamiast kompletnego przeprogramowania logiki równoważności.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Treap — Randomized Balanced BST i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.