Wyobraź sobie czerwono-czarne drzewo. Czy zawsze istnieje sekwencja wstawiania i usuwania, która ją tworzy?

Załóżmy następującą definicję drzewa czerwono-czarnego:

Jest to drzewo wyszukiwania binarnego.
Każdy węzeł ma kolor czerwony lub czarny. Korzeń jest czarny.
Dwa węzły połączone krawędzią nie mogą być jednocześnie czerwone.
Oto dobra definicja liścia NIL, jak na wiki. Liść NIL ma kolor czarny.
Ścieżka od korzenia do dowolnego liścia NIL zawiera tę samą liczbę czarnych węzłów.

Pytanie

Załóżmy, że zaimplementowano operacje inserti deletedla drzewa czerwono-czarnego. Teraz, jeśli otrzymasz prawidłowe czerwono-czarne drzewo, czy zawsze istnieje sekwencja inserti deleteoperacje, które je konstruują?

Motywacja

To pytanie jest motywowane tym pytaniem i dyskusją z tego pytania .

Osobiście uważam, że jeśli wyobrażasz sobie prawidłowe czerwono-czarne drzewo składające się tylko z czarnych węzłów (co oznacza, że wyobrażasz sobie idealnie zrównoważone drzewo), istnieje sekwencja inserti deleteoperacje, które je konstruują. Jednak,

Nie wiem, jak dokładnie to udowodnić
Interesuje mnie również bardziej ogólny przypadek

data-structures search-trees balanced-search-trees alisianoi
źródło

Twoje pytanie brzmi trochę kołowo ... każdy zestaw operacji wstawiania i usuwania utworzy czerwono-czarne drzewo ... dosłownie cokolwiek, ponieważ czerwono-czarny jest tylko definicją. Czy twoje pytanie ogranicza się do czysto czarnego drzewa?

JOX,

Nie, myślę, że źle zrozumiałeś. Oczywiście każdy zestaw wstawek i usunięć tworzy niektóre czerwono-czarne drzewa. Pytanie brzmi: czy każde drzewo, które pasuje do definicji, można zbudować za pomocą sekwencji wstawiania i usuwania? Jeśli otrzymasz jakieś drzewo, czy możesz odtworzyć sekwencję wstawiania i usuwania?

alisianoi

@ all3fox Tak, masz rację. Istnieje algorytm, który wykorzystuje tę operację inserti deletekonstruuje prawidłowe czerwono-czarne drzewo składające się tylko z czarnych węzłów . Używa wstawek / usunięć, aby utworzyć drzewo wysokości . Najpierw możemy stworzyć idealnie zrównoważone czerwono-czarne drzewo w pierwszej kolejności, używając wstawek, a następnie używając i tyle samo usunięć odmalowujemy je całkowicie czarne drzewo. Sztuką jest poruszanie się w górę razy najniższej czerwonej warstwy w górę drzewa, aż dotrze do korzenia.

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$

h

$h$

Anton Trunov,

@AntonTrunov dziękuję, rozumiem to. A co z przypadkiem ogólnego Czerwono-Czarnego Drzewa? Jak myślisz, czy można zbudować dane drzewo czerwono-czarne za pomocą inserti deleteoperacji?

alisianoi

a) Odpowiedź będzie zależeć od dokładnego wdrożenia inserti delete; może istnieć kilka sposobów wykonania tych operacji. b) Ponieważ drzewa RB są zasadniczo drzewami B rzędu 4, można tam szukać inspiracji. Szczegóły mogą okazać się trudne, ponieważ mapowanie z RB na B (i / lub wstecz) nie jest unikalne.

Raphael

Odpowiedzi:

Operacje wstawiania i usuwania w drzewie czerwono-czarnym obejmują równoważenie potrzebne do zachowania właściwości czerwono-czarnego.

Problem z niekrzywymi (lewymi lub prawymi) pochylonymi czerwonymi czarnymi drzewami polega na tym, że istnieje wiele sposobów przywrócenia czerwono-czarnej czerni po podstawowym usunięciu lub wstawieniu.
To nie wstawka lub usunięcie przekształca drzewo, ale ponowne zrównoważenie i obrót, które następują później, aby zachować / przywrócić czerwoną czerń drzewa.

Podstawowy opis czerwono-czarnego drzewa nie określa, którą z możliwych dróg wybrać.
Nie jest możliwe, aby dowiedzieć się, jak dokładnie zrekonstruować dane czerwono czarne drzewo, ponieważ ponowne zrównoważenie nie musi być deterministyczne.

Zostało to „rozwiązane” w przypadku pochylonych w lewo czerwonych czarnych drzew.
Jest tylko jeden sposób przeprowadzenia równoważenia. Tak więc każde odchylone czerwone czarne drzewo można odtworzyć za pomocą wstawek i skasowań, ponieważ ponowne równoważenie / obroty są wykonywane w określony, deterministyczny sposób.

Nie oznacza to, że lewostronne drzewa RB są lepsze lub bardziej wydajne, co zyskują z jednej strony dzięki deterministycznym regułom równoważenia, z drugiej tracą przez bardziej złożony kod równoważący.

Zgodnie z komentarzem @ Antona:
Istnieje algorytm, który wykorzystuje operację wstawiania i usuwania w celu skonstruowania prawidłowego czerwono-czarnego drzewa składającego się tylko z czarnych węzłów. Wykorzystuje wstawiania / usuwania w celu utworzenia drzewa o wysokości . Najpierw możemy stworzyć idealnie zrównoważone czerwono-czarne drzewo w pierwszej kolejności przy użyciu wstawek , a następnie przy użyciu wstawek i tej samej ilości usunięć odmalowujemy je całkowicie czarne drzewo. Sztuką jest poruszanie się w górę razy najniższej czerwonej warstwy w górę drzewa, aż dotrze do korzenia. $(h+2)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$

Myślę jednak, że kompletny algorytm równoważenia, taki jak Day-Stout-Warren, byłby bardziej wydajny.

Johan
źródło

Korzystając z operacji insertiz deleteksiążki CLRS, możesz zbudować prawidłowe drzewo RB składające się tylko z czarnych węzłów . Sztuką jest wstawienie większej liczby węzłów niż potrzeba, a następnie usunięcie nadmiernych. Algorytm będzie wyeliminować czerwone węzły.

Anton Trunov

@AntonTrunov, czy masz link do tego algorytmu, dobrze byłoby dołączyć go do odpowiedzi. Nie mogę go znaleźć za pomocą mojego google-fu.

Johan

Niestety nie mam linku. Próbowałem wtedy odpowiedzieć na pytanie i opracowałem algorytm dla specjalnego przypadku wszystkich czarnych drzew RB. Opisałem to w tym komentarzu, ale nie dostarczyłem dowodu.

Anton Trunov

Co masz na myśli przez „Zostało to„ rozwiązane ”z pochylonymi w lewo czerwonymi czarnymi drzewami.”. Nawet pochylone w lewo czerwone czarne drzewo ma wiele sposobów przechowywania tych samych przedmiotów.

user239558,