Pokoloruj drzewo binarne, aby było czerwono-czarnym drzewem

Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL).

Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami.

Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z węzłami NULL), czy istnieje „szybki” algorytm, który może określić, czy możemy pokolorować (i znaleźć kolorystykę) węzłów czerwony / czarny, aby spełniały wszystkie właściwości drzewa czerwono-czarnego (definicja jak w tym pytaniu )?

Początkowa myśl była taka, że możemy po prostu usunąć węzły NULL i spróbować rekurencyjnie zweryfikować, czy powstałe drzewo może być drzewem czerwono-czarnym, ale wydaje się, że nigdzie nie poszło.

Przeprowadziłem (krótkie) wyszukiwanie artykułów w Internecie, ale nie mogłem znaleźć żadnych, które mogłyby rozwiązać ten problem.

Możliwe, że brakuje mi czegoś prostego.

— Aryabhata
źródło

Jestem prawie pewien, że drzewo może mieć kolor czerwono-czarny iff dla każdego węzła, najdłuższa ścieżka od niego do węzła NULL jest nie więcej niż dwa razy dłuższa niż najkrótsza. Czy to wystarczająco szybko?

— Karolis Juodelė,

Odpowiedzi:

Jeśli dla każdego węzła drzewa najdłuższa ścieżka od niego do węzła liścia jest nie więcej niż dwa razy dłuższa niż najkrótsza, drzewo ma czerwono-czarne zabarwienie.

Oto algorytm określający kolor dowolnego węzła n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Oto n.black-quotaliczba czarnych węzłów, których oczekujesz, że dojdą do liścia, od węzła, ni n.min-heightodległość do najbliższego liścia.

Dla zwięzłości zapisu niech , i . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Twierdzenie: Fix binarnego drzewa . Jeżeli dla każdego węzła , i dla węzła , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ a następniema czerwono-czarne zabarwienie z dokładnieczarnymi węzłami na każdej ścieżce od korzenia do liścia. $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

Dowód: indukcja powyżej . $b(n)$

Sprawdź, czy wszystkie cztery drzewa wysokości jednego lub dwóch spełniają twierdzenie . $b(n) = 1$

Z definicji drzewa czerwono-czarnego korzeń jest czarny. Niech będzie węzłem z czarnym rodzicem takim, że $n$ $p$ . Następnie,oraz. $b(p) \in [\frac{1}{2}h(p), m(p)]$ $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

Załóżmy, że twierdzenie to obowiązuje dla wszystkich drzew o korzeniu , . $r$ $b(r) < b(q)$

Jeśli , to może być zabarwione na czerwono-czarny kolor przez założenie indukcyjne. $b(n) = m(n)$ $n$

Jeśli a następnie $b(p) = \frac{1}{2}h(p)$ . nie spełnia założenia indukcyjnego i dlatego musi być czerwony. Niechbędzie dzieckiem. oraz $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ . Wtedymoże być czerwono-czarne według założenia indukcyjnego. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Zauważ, że z tego samego powodu, jeżeli , a następnie zarównojaki dzieckospełniają założenie indukcyjne. Dlategomoże mieć dowolny kolor. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

— Karolis Juodelė
źródło

@Aryabhata, każde przejście jest w porządku, o ile rodzic jest widziany przed dziećmi. Nie mam formalnego dowodu, ale mam pojęcie, jak by to wyglądało. Spróbuję coś napisać, kiedy będę mógł.

— Karolis Juodelė

@Aryabhata, dodałem dowód. Przepraszam, że zajęło mi to tak długo.

— Karolis Juodelė

@Aryabhata, chodzi o to, że jeśli

jakiegoś węzła

ma określone granice, dziecko lub wnuk

może mieć

w tych samych granicach. Posiadanie

w tych granicach może odpowiadać

będącemu czarnemu. Większość dowodów dotyczy ograniczenia

dziecka lub wnuka, biorąc pod uwagę

, lewe dziecko jest czarne, a prawe dziecko jest czerwone, ścieżka o długości 16 to

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$

h

$h$

m

$m$

h

$h$ oraz

rodzica lub dziadka. Twoje drzewo z pewnością można pokolorować.

m

$m$

b (r o o t) = 8

$b(root) = 8$

ścieżka o długości 8 to

, ścieżki 9 i 12 mogą mieć wiele prawidłowych kolorów.

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

— Karolis Juodelė

Jest pytanie dotyczące tej odpowiedzi .

— David Richerby,

Uważam, że odpowiedź Karolis jest poprawna (i całkiem ładna charakterystyka czerwono-czarnych drzew, podając algorytm czasu ), po prostu chciałam dodać kolejną możliwą odpowiedź. $O(n)$

Jednym z podejść jest zastosowanie programowania dynamicznego.

Biorąc pod uwagę drzewo, dla każdego węzła konstruujesz dwa zestawy: i które zawierają możliwe czarne wysokości dla poddrzewa zakorzenionego w . zawiera czarne wysokości, zakładając, że ma kolor czerwony, a zakłada, że ma kolor czarny. $n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

Teraz podane zestawy dla i (tj. Bezpośrednie potomki ), możemy obliczyć odpowiednie zestawy dla , biorąc odpowiednie skrzyżowania i związki (i zwiększając w razie potrzeby). $n.Left$ $n.Right$ $n$ $n$

Wydaje mi się, że jest to algorytm czasu . $O(n \log n)$

— Aryabhata
źródło