Scalenie dwóch drzew wyszukiwania binarnego

Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego typu algorytmu wydaje się być w kolejności, O(n+m)gdzie ni msą wielkości odpowiednio każdego drzewa.

Powiedziano mi jednak, że można to zrobić w miejscu O(h), gdzie hjest wysokość drzewa o większej wysokości. I jestem całkowicie zagubiony, jak to jest możliwe. Próbowałem najpierw eksperymentować z obracaniem jednego drzewa, ale obrócenie drzewa do kręgosłupa to już O (h).

ds.algorithms ds.data-structures tree efritz
źródło

Nie wiem, erick, mam też to samo pytanie.

Szczerze mówiąc, było to pytanie zadane w zadaniu domowym Algorytmy. Okazuje się, że O (h) jest zbyt rygorystyczne dla środowiska wykonawczego, ponieważ pytanie zapomniało podać bardziej niezbędne informacje: że wszystkie klucze z jednego drzewa były mniejsze niż wszystkie klucze z prawego drzewa.

efritz

Czy czegoś brakuje? Czy połączenie drzew binarnych nie byłoby łatwe O(log n)dzięki prostej funkcji przenoszenia węzła?

@AT Tak, ale nie wiedzieliśmy, że klucze z jednego BST wzajemnie się wykluczają.

efritz

To jest czerwono-czarne drzewo, a nie BST. Czerwona czerń (a także drzewa AVL i hałdy) to specjalne rodzaje drzew, które zachowują właściwości związane z wysokością. Waniliowe BST mogą być pojedynczym kręgosłupem. Spróbuj wstawić do BST nie malejącą lub nie rosnącą serię liczb, a zobaczysz, że wysokość tych drzew jest w rzeczywistości n. Tylko pełne lub pełne drzewa binarne mają logarytmiczną wysokość w stosunku do całkowitej liczby węzłów.

efritz

Odpowiedzi:

W ArXiv: 1002.4248 John Iacono i Özgür Özkan opisują stosunkowo prosty algorytm scalania dwóch drzew wyszukiwania binarnego w czasie zamortyzowanym ; analiza jest najtrudniejsza. [ Aktualizacja: Jak Joe słusznie zauważa w swojej odpowiedzi, algorytm ten jest spowodowany przez Browna i Tarjana.] Opisują również bardziej skomplikowaną strukturę danych słownika, opartą na stronniczych listach pominięć, która obsługuje scalanie w czasie zamortyzowanym . $O(\log^2 n)$ $O(\log n)$

Z drugiej strony, ograniczenie w najgorszym przypadku jest niemożliwe. Rozważmy dwa drzewa wyszukiwania binarnego z węzłami, jedno przechowujące parzyste liczby całkowite między a , drugie przechowujące nieparzyste liczby całkowite między a . Scalenie dwóch drzew tworzy nowe drzewo wyszukiwania binarnego, przechowujące wszystkie liczby całkowite od do . W każdym takim drzewie stały ułamek węzłów ma inną parzystość niż ich rodzice. (Dowód: rodzic nieparzystego liścia musi być parzysty.) Zatem połączenie drzew parzystych i nieparzystych wymaga zmiany $O(\log n)$ $n$ $2$ $2n$ $1$ $2n-1$ $1$ $2n$ . $\Omega(n)$

Jeffε
źródło

Jedna uwaga: jeśli poprawnie przeczytałem opis w tym dokumencie, drzewa te nie obsługują wstawiania i usuwania.

scalania tylko następujące procedury wyszukiwania połączenia palec drzew (opisanego w odpowiedzi Joe). Ograniczony zestaw operacji pozwala na lepszą analizę niż

O (\lg^{2} n)

$O(\lg^2 n)$

jeden.

O (n \lg \frac{m}{n})

$O(n \lg \frac{m}{n})$

jbapple

Ulepszona analiza wynika z amortyzacji, a nie ograniczenia dozwolonych operacji. Insercje i delecje mogą być obsługiwane pęknięć i łączy (faktycznie „łączy się”), w tym samym

amortyzowana razem złączone.

O (l o g n)

$O(log n)$

Jeffε

Z ciekawości, czy czas

zostaje zmieniony, jeśli drzewa są przechowywane w tablicach zamiast w listach połączonych (co, jak zakładam, miałeś na myśli mówiąc „zmieniając ... wskaźniki ”)?

Ω (n)

$\Omega(n)$

mtahmed

Domyślnie „drzewa wyszukiwania binarnego” są strukturami opartymi na wskaźnikach (a nie „listach połączonych”); każdy węzeł wskazuje na dwoje dzieci i prawdopodobnie na jego rodzica. Ale dolna granica nie zależy od dokładnej reprezentacji. Są

sposoby scalania dwóchdrzewek wyszukiwania binarnego

węzłowego, więc każdy algorytm porównawczy wymaga co najmniej

(\binom{2 n}{n})

$\binom{2n}{n}$

n

$n$

porównania, aby wybrać właściwe.

\log_{2} (\binom{2 n}{n}) \geq 2 n - O (\log n)

$\log_2 \binom{2n}{n} \ge 2n - O(\log n)$

Jeffε

@ Jɛ ﬀ E: Zgadzam się, że podziały i złączenia są obsługiwane, ale nie sądzę, że tworzenie lub niszczenie drzew jest. Na przykład, jeśli chcę usunąć „x” z alfabetu, nie otrzymuję tylko „a..wyz”, ale także „x”. Rozmiar wszechświata (który jest

, patrz sekcja 2.1) nie zmienia się. Również wstęp do sekcji 1 zauważa, że zestawy muszą podzielić wszechświat, co interpretuję (być może niepoprawnie), aby oznaczać, że każdy element we wszechświecie znajduje się w jakimś drzewie. Tak więc, jak go czytam, ta konstrukcja nie działa na nieograniczonych wszechświatach. Tak powinienem napisać mój komentarz powyżej.

n

$n$

jbapple

Pomocne może okazać się to odniesienie: Brown and Tarjan, A Fast Merging Algorytm , w którym autorzy pokazują, jak scalać zrównoważone drzewa binarne (AVL) w który jest optymalny (dla algorytmów porównawczych). isą długościami posortowanych list reprezentowanych przez przeszukiwanie binarne drzew, i zakłada się, że. $O(n \log \frac{m}{n})$ $m$ $n$ $m \geq n$

Dyskusję na temat różnych technik łączenia uporządkowanych zestawów można również znaleźć w sekcji 11.5 tego artykułu na drzewach wyszukiwania palcami

Joe
źródło

O (n \log \frac{m}{n})

$O(n\log \frac{m}{n})$

m \geq n

$m\ge n$

Myślałem, że wynika to z upływu czasu, ale zredagowałem pytanie, aby było jasne.

Joe

$\bf\mathcal{O}(1)$ $\mathcal{O}(log\ n)$

Brodal, Gerth Stølting, Christos Makris i Kostas Tsichlas. „Czysto funkcjonalne najgorsze przypadki w stałych sortowanych listach w ustalonym czasie” . W materiałach z 14. konferencji dotyczącej dorocznego europejskiego sympozjum - Tom 14, 172–183. ESA'06. Londyn, Wielka Brytania, Wielka Brytania: Springer-Verlag, 2006. [ PDF ]

W
źródło

Ich struktura danych obsługuje łączenie w czasie zamortyzowanym O (1), a nie scalanie. Wszystkie elementy w jednym drzewie muszą być mniejsze niż wszystkie elementy w drugim.

Jeffε

T_{i}

$T_i$

T_{j}

$T_j$

T_{i}

$T_i$

T_{j}

$T_j$

T_{j}

$T_j$

T_{i}

$T_i$

w (T_{i}) = w (T_{j})

$w(T_i) = w(T_j)$

T_{j}

$T_j$

T_{i}

$T_i$

T_{i} \cdot T_{j}

$T_i \centerdot T_j$

T_{i}

$T_i$