Szybsze łączenie struktur danych podobnych do pułapek o mniej więcej tym samym rozmiarze

Biorąc pod uwagę dwa drzewa AVL i T 2 oraz wartość t r taką, że ∀ x ∈ T 1 , ∀ y ∈ T 2 , x < t r < y , łatwo jest zbudować nowe drzewo AVL zawierające t r i wartości w T 1 i T 2 w czasie O ( 1 + | h ( T 1 ) - h ( $T_1$$T_2$$t_r$$\forall x \in T_1, \forall y \in T_2, x < t_r < y$$t_r$$T_1$$T_2$ , gdzie h ( T ) oznacza wysokość drzewa T (o ile drzewa przechowują swoją wysokość).$O(1+|h(T_1) - h(T_2)|)$$h(T)$$T$

Jest to również możliwe w przypadku drzew czerwono-czarnych i zakładam również wiele innych rodzajów drzew zrównoważonych.

Czy jest to możliwe w przypadku pułapek lub struktur danych podobnych do pułapek? Co jeśli pominiemy ?$t_r$

Papier treaps w Algorytmice pokazuje, jak to zrobić w oczekiwany czas. Jeśli istnieje sposób na wykonanie O (1) oczekiwanego łączenia na pułapkach (lub strukturach podobnych do pułapek) o mniej więcej tym samym rozmiarze (lub priorytecie root), myślę, że można użyć sztuczki Kaplana i Tarjana podczas ładowania grzbiety w celu tworzenia pułapek (lub struktur danych podobnych do pułapek) z podwójnie logarytmicznym złączeniem.$O(\min(h(T_1),h(T_2)))$

Nie, nie można tego zrobić za pomocą zwykłych pułapek, jeśli priorytety są losowe.

Dokładna roszczenie Zrobię to, że do wykonania takiego scalenia dwóch jednakowo wielkości treaps z przypadkowymi priorytetów wymaga aktualizacji wskaźniki w oczekiwaniu.$\Theta(\log n)$

Oto szkic wstępny:

Rozważ liczbę wskaźników, które musisz zmienić w oczekiwaniu na wykonanie operacji. Łatwiej jest udowodnić ograniczenie jeśli nie wstawimy t r, ale po prostu połączymy T 1 i T 2 . Rozważ prawy kręgosłup S 1 z T 1 i lewy kręgosłup S 2 z T 2 . Pokoloruj elementy S 1 na czerwono i S 2 na niebiesko. Zamów S 1 ∪ S $\Theta(\log n)$$t_r$$T_1$$T_2$$S_1$$T_1$$S_2$$T_2$$S_1$$S_2$$S_1 \cup S_2$według priorytetu. Musimy zmieniać wskaźnik za każdym razem, gdy zmienia się kolor w tej sekwencji. Ponieważ oba kolce mają rozmiar z dużym prawdopodobieństwem, a priorytety są przypadkowe, to nie jest zbyt trudne, aby zobaczyć, że # zmian kolorów w sekwencji jest Θ ( log n ) . Musimy więc zaktualizować wskaźniki Θ ( log n ) dla scalenia (bez dodawania t r ).$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$t_r$

Teraz dodanie podczas scalania niewiele pomaga. Liczbę zmian wskaźnika w tym przypadku można ograniczyć w następujący sposób: Kolejność S 1 ∪ S 2 ∪ { t r } według priorytetu. Usuń wszystko mniej niż t r w sekwencji. Wówczas # zmian kolorów w wynikowej sekwencji jest naszą dolną granicą. Ponieważ t r ma losowy priorytet, oczekiwana wysokość poddrzewa zakorzenionego w nim w końcowej pułapce wynosi O ( 1 ) , więc ma tylko węzły O ( 1 ) S $t_r$$S_1 \cup S_2 \cup \{t_r\}$$t_r$$t_r$$O(1)$$O(1)$ z niższym priorytetem niż oczekiwany, dlategopodczas dodawania t r straciliśmy tylkozmiany wskaźnika O ( 1 ) w naszej dolnej granicy.$S_1 \cup S_2$$O(1)$$t_r$

To powiedziawszy, prawdopodobnie istnieje sposób na uzyskanie struktury danych przypominającej pułapki, która pozwala na ciągłe łączenie oczekiwanego czasu.

Aktualizacja: zobacz poniżej aktualizację dotyczącą nieprawidłowości tej operacji łączenia

Oto bardzo przybliżony szkic możliwego rozwiązania:

Myślę, że mogę rozwiązać ten problem, używając pewnego rodzaju losowo zrównoważonego drzewa B +. Podobnie jak pułapki, drzewa te mają unikalną reprezentację. W przeciwieństwie do pułapek przechowują niektóre klucze wiele razy. Można to naprawić za pomocą sztuczki z „Biased Search Trees” Benta i innych, polegającej na przechowywaniu każdego klucza tylko na najwyższym (tj. Najbliższym rootowi) poziomie, na którym się pojawia)

Drzewo dla uporządkowanego zestawu unikalnych wartości jest tworzone przez pierwsze skojarzenie każdej wartości ze strumieniem bitów, podobnie do sposobu, w jaki każda wartość w pułapce jest powiązana z priorytetem. Każdy węzeł w drzewie zawiera zarówno strumień klucza, jak i strumień bitów. Węzły inne niż liście zawierają ponadto liczbę naturalną wskazującą wysokość drzewa zakorzenionego w tym węźle. Wewnętrzne węzły mogą mieć dowolną niezerową liczbę dzieci. Podobnie jak drzewa B +, każda nie przecinająca się ścieżka od korzenia do liścia ma tę samą długość.

$v$$k$$i$$v$$k$$i+1$$v$$v$$i$$1$$v$$i$

Aby utworzyć drzewo z posortowanej listy kluczy ze skojarzonymi strumieniami bitów, najpierw zbierz klucze do ciągłych grup na podstawie pierwszego bitu w ich strumieniach. Dla każdej z tych grup utwórz element nadrzędny ze strumieniem klucza i bitów największego klucza w grupie, ale z pominięciem pierwszego bitu strumienia. Teraz wykonaj tę samą procedurę grupowania nowych rodziców, aby utworzyć dziadków. Kontynuuj, aż pozostanie tylko jeden węzeł; to jest korzeń drzewa.

Poniższa lista kluczy i (bitów) strumieni bitów jest reprezentowana przez drzewo poniżej. W prefiksach strumienia bitów „.” znaczy trochę Oznacza to, że dowolny strumień bitów dla klucza A z 0 na pierwszym miejscu daje takie samo drzewo jak każdy inny, zakładając, że strumień bitów innego klucza nie jest inny.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Każde dziecko określonego węzła wewnętrznego ma ten sam bit na pierwszym miejscu swojego strumienia bitów. Nazywa się to „kolorem” rodzica - 0 to czerwony, 1 to zielony. Dziecko ma „smak” w zależności od pierwszego kawałka strumienia bitów - 0 to wiśnia, 1 to mięta. Liście mają smaki, ale nie mają koloru. Z definicji węzeł wiśniowy nie może mieć zielonego elementu nadrzędnego, a węzeł mięty nie może mieć czerwonego elementu nadrzędnego.

$n$$2^{1-n}$ ${n-1}\choose{i-1}$ a oczekiwana wartość to $(n+1)/2$. Dla wszystkich$n \geq 2$, to jest $\leq \frac{3}{4}n$, więc oczekiwana wysokość drzewa wynosi $O(\lg n)$.

Aby połączyć dwa drzewa o równej wysokości, najpierw sprawdź, czy ich korzenie są tego samego koloru. Jeśli tak, oderwij od lewego korzenia jego najbardziej potomne dziecko, a od prawego korzenia jego lewe dziecko, a następnie rekurencyjnie połącz te dwa drzewa. Rezultatem będzie drzewo o tej samej wysokości lub o jeden wyższy, ponieważ drzewa mają ten sam smak (patrz poniżej). Jeśli wynik rekurencyjnego łączenia dwóch drzew ma taką samą wysokość jak dwa odcięte dzieci, uczyń je środkowym dzieckiem korzenia z pozostałymi dziećmi lewego korzenia przed nim, a pozostałymi dziećmi prawego korzenia za nim. Jeśli jest wyższy o 1, uczyń jego dzieci środkowymi dziećmi korzenia z pozostałymi dziećmi lewego korzenia przed nim, a pozostałymi dziećmi prawego korzenia za nim. Jeśli korzenie mają różne kolory, sprawdź, czy mają ten sam smak. Jeśli to zrobią, nadaj im nowego rodzica ze strumieniem klucza i bitów odpowiedniego katalogu głównego, unikając pierwszego bitu. Jeśli nie, daj każdemu rootowi nowego rodzica ze strumieniem klucza i bitów starego roota (unikając każdego pierwszego bitu), a następnie rekurencyjnie dołącz do tych drzew.

There are two recursive calls in this algorithm. The first is when the roots have the same color, the second is when the roots have different colors and different flavors. The roots have the same color with probability $1/2$. The recursive call in this case always sees roots with the same flavor, so the second type of recursion never occurs after the first. However, the first can occur repeatedly, but each time with probability $1/2$, so the expected running time is still $O(1)$. The second recursive call happens with probability $1/4$, and subsequent recursive calls are always on trees with different colors, so the same analysis applies.

Aby połączyć dwa drzewa o nierównej wysokości, najpierw przeszukaj lewy kręgosłup prawego drzewa, zakładając, że prawe drzewo jest wyższe. (Drugi przypadek jest symetryczny). Po osiągnięciu dwóch drzew o równej wysokości wykonaj operację łączenia dla dwóch drzew o równej wysokości, zmodyfikowanych w następujący sposób: Jeśli wynik ma tę samą wysokość, zastąp drzewo, które było dzieckiem, wynikiem dołączenia. Jeśli wynik jest wyższy, dołącz element nadrzędny drzewa po prawej stronie do katalogu głównego drugiego drzewa, po tym, jak zostanie on podniesiony o jeden przez dodanie elementu nadrzędnego dla katalogu głównego. Drzewo będzie prawdopodobnie tej samej wysokości$1/2$, więc to kończy się w $O(1)$ spodziewany.

Update: Thanks to QuickCheck, I discovered that the above join method does not produce the same trees as the uniquely represented trees above. The problem is that parent choices near the leaves may change depending on the available siblings. To fix up those changes, join would have to traverse all the way to the leaves, which is not $O(1)$. Here is the example QuickCheck found:

a 01110
b 110..
c 10...
d 00000

The the tree made by [a,b] has height 2, the tree made by [c,d] has height 2, and the tree made by joinEqual (tree [a,b]) (tree [c,d]) has height 3. However, the tree made by [a,b,c,d] has height 5.

Here is the code I used to find this error.