Podzakres drzewa czerwonego i czarnego

Próbując naprawić błąd w bibliotece, bezskutecznie szukałem artykułów na temat znajdowania podzakresów na czerwonych i czarnych drzewach. Zastanawiam się nad rozwiązaniem wykorzystującym zamki błyskawiczne i czymś podobnym do zwykłej operacji dołączania stosowanej w algorytmach usuwania niezmiennych struktur danych, ale wciąż zastanawiam się, czy istnieje lepsze podejście, którego nie udało mi się znaleźć, a nawet jakaś minimalna granica złożoności na takiej operacji?

Dla jasności mówię o algorytmie, który, biorąc pod uwagę czerwono-czarne drzewo i dwie granice, stworzy nowe czerwono-czarne drzewo ze wszystkimi elementami pierwszego drzewa, które należą do tych granic.

Oczywiście górną granicą złożoności byłaby złożoność przemierzania jednego drzewa i konstruowania drugiego przez dodawanie elementów.

Ta odpowiedź łączy niektóre moje komentarze do pytania i je rozszerza.

Operację podzakresu na drzewach czerwono-czarnych można wykonać w najgorszym przypadku O (log n), gdzie n jest liczbą elementów w oryginalnym drzewie. Ponieważ powstałe drzewo będzie dzielić niektóre węzły z oryginalnym drzewem, to podejście jest odpowiednie tylko wtedy, gdy drzewa są niezmienne (lub drzewa są zmienne, ale oryginalne drzewo nie jest już potrzebne).

Najpierw zauważ, że operacja podzakresu może być zaimplementowana przez dwie operacje podziału. Tutaj operacja podziału bierze czerwono-czarne drzewo T i klucz x i wytwarza dwa drzewa L i R tak, że L składa się ze wszystkich elementów T mniejszych niż x, a R elementów T większych niż x. Dlatego naszym celem jest teraz wdrożenie operacji podziału na drzewach czerwono-czarnych w najgorszym przypadku O (log n).

Jak wykonujemy operację podziału na drzewach czerwono-czarnych w czasie O (log n)? Okazało się, że istnieje dobrze znana metoda. (Nie wiedziałem o tym, ale nie jestem ekspertem od struktur danych.) Rozważmy operację łączenia , która bierze dwa drzewa L i R w taki sposób, że każda wartość w L jest mniejsza niż każda wartość w R i tworzy drzewo składające się ze wszystkich wartości w L i R. Operacja łączenia może być zaimplementowana w najgorszym przypadku O (| r _L -r _R | +1), gdzie r _L i r _Rsą odpowiednio rzędami L i R (to znaczy liczbą czarnych węzłów na ścieżce od korzenia do każdego liścia). Operację podziału można wykonać za pomocą operacji łączenia O (log n) razy, a całkowity czas najgorszego przypadku nadal wynosi O (log n), biorąc pod uwagę sumę teleskopową.

W sekcjach 4.1 i 4.2 książki [Tar83] autorstwa Tarjana opisano, jak wykonać operacje łączenia i podziału na drzewach czerwono-czarnych w najgorszym przypadku O (log n). Implementacje te niszczą oryginalne drzewa, ale łatwo je przekonwertować na niezmienne, funkcjonalne implementacje, kopiując węzły zamiast je modyfikując.

Na marginesie, moduły Set i Map Objectl Caml zapewniają operację podziału, a także inne standardowe operacje na (niezmiennych) zrównoważonych drzewach wyszukiwania binarnego. Chociaż nie używają drzewek czerwono-czarnych (używają zrównoważonych drzewek wyszukiwania binarnego z tym, że lewa wysokość i prawa wysokość różnią się co najwyżej o 2), warto również spojrzeć na ich implementacje. Oto implementacja modułu Set .

Bibliografia

[Tar83] Robert Endre Tarjan. Struktury danych i algorytmy sieciowe . Tom 44 CBMS-NSF Regional Conference Series in Applied Mathematics , SIAM, 1983.

Rozwiązaniem nie jest stosowanie czerwono-czarnych drzew. W drzewach splay i AVL kod do dzielenia i łączenia jest bardzo prosty. Odsyłam cię do następujących adresów URL z kodem Java dla drzew splay i drzew AVL, które to obsługują. Przejdź do następującego adresu URL i sprawdź Set.java (drzewa avl) i SplayTree.java (drzewa splay).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

--- Danny Sleator

(To ma być komentarz, ale jestem zbyt nowy, aby zostawić komentarz.)

Chciałbym jedynie zauważyć, że możesz być również zainteresowany operacją „wycięcia”, która zwraca podzakres jako nowe drzewo, a drzewo wejściowe bez podzakresu jako inne. Musisz jednak kontrolować podstawową reprezentację drzewa, ponieważ znana metoda opiera się na łączach poziomu. Wycięcie przebiega logarytmicznie w czasie do wielkości mniejszego drzewa, aczkolwiek w sensie zamortyzowanym („zamortyzowany” to „cyrk”, ponieważ nie mam już dostępu do papieru) Zobacz:

K. Hoffman, K. Mehlhorn, P. Rosenstiehl i RE Tarjan, Sortowanie sekwencji Jordana w czasie liniowym za pomocą drzew wyszukiwania powiązanego z poziomem, Informacja i kontrola, 68 (1986), 170–184

PS Powyższy cytat pochodzi z zapisu tref Seidela. Pułapki obsługują również wycięcie.

$n$$m$$[a,b]$

1. $O(\lg n)$$\ge a$$a$
2. $O(m)$
3. $O(m)$

$O(m+\lg n)$$O(n+m\lg m)$

$o(m)$$\Omega(\lg m)$$k$$\lg m$

Nie wypracowałem szczegółów, więc nie jestem pewien, jak dodatkowe księgowanie wpływa na czas działania.

$O(1)$$\Omega(\lg m)$