Nie wszystkie drzewa czerwono-czarne są zrównoważone?

Intuicyjnie „zrównoważone drzewa” powinny być drzewami, w których lewe i prawe podgrzewa w każdym węźle muszą mieć „w przybliżeniu taką samą” liczbę węzłów.

Oczywiście, gdy mówimy o zrównoważeniu czerwono-czarnych drzew * (patrz definicja na końcu), faktycznie mamy na myśli, że są one zrównoważone wysokościowo iw tym sensie są zrównoważone.

Załóżmy, że próbujemy sformalizować powyższą intuicję w następujący sposób:

Definicja: Drzewo binarne nazywa się -balanced, z , jeśli dla każdego węzła nierówność $\mu$ $0 \le \mu \leq \frac{1}{2}$ $N$

$μ \leq \frac{| N_{L} | + 1}{| N | + 1} \leq 1 - μ$ $\mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$
wstrzymuje i dla każdego istnieje jakiś węzeł, dla którego powyższa instrukcja zawodzi. jest liczbą węzłów w lewym poddrzewie ito liczba węzłów pod drzewem z jako rootem (w tym rootem). $\mu' \gt \mu$ $|N_L|$ $N$ $|N|$ $N$

Sądzę, że w literaturze na ten temat nazywane są drzewami o zrównoważonej masie .

Można pokazać, że jeśli drzewo binarne z węzłów jest zrównoważone (dla stałej ), wówczas wysokość drzewa wynosi , utrzymując w ten sposób ładne wyszukiwanie nieruchomości. $n$ $\mu$ $\mu \gt 0$ $\mathcal{O}(\log n)$

Pytanie brzmi:

Czy jest jakieś takie, że każde wystarczająco duże czerwono-czarne drzewo jest zrównoważone? $\mu \gt 0$ $\mu$

Stosujemy definicję drzew czerwono-czarnych (od Wstęp do algorytmów Cormena i in.):

Drzewo wyszukiwania binarnego, w którym każdy węzeł ma kolor czerwony lub czarny i

Korzeń jest czarny
Wszystkie węzły NULL są czarne
Jeśli węzeł jest czerwony, wówczas oba jego dzieci są czarne.
Dla każdego węzła wszystkie ścieżki od tego węzła do potomnych węzłów NULL mają tę samą liczbę czarnych węzłów.

Uwaga: nie liczymy węzłów NULL w powyższej definicji balanced. (Chociaż uważam, że nie ma znaczenia, jeśli to zrobimy). $\mu$

data-structures binary-trees search-trees

— Aryabhata
źródło

@Aryabhata: co jest takiego wyjątkowego (

) w twojej edycji? Nic mi nie jest z tym, że zrównoważony oznacza zrównoważony. Nie sądzę, że powinieneś znaleźć dokładną aby udowodnić, że wysokość to . Czy coś brakuje?

μ^{'} > μ

$\mu'>\mu$

\frac{1}{3}

$\frac13$

\frac{1}{4}

$\frac14$

μ

$\mu$

O (\log n)

$O(\log n)$

— jmad

Ponadto potrzebujesz negatywnego wyrażenia, aby zapewnić łańcuch kontrprzykładu z jednym drzewem dla każdego . Jakikolwiek łańcuch nieskończony, który nie zmniejsza wielkości węzła, byłby wystarczający, prawda?

n \in N

$n \in \mathbb{N}$

— Raphael

@jmad: Bez edycji każde drzewo jest trywialnie zbalansowane więc nie mamy trywialnej odpowiedzi na pytanie. Chciałem tego uniknąć.

μ^{'}

$\mu'$

0

$0$

— Aryabhata

@Raphael: Nie rozumiem. Rozmiar węzła drzewa wynosi . Mówisz, że nie ma znaczenia, jakie drzewo wybieramy dla i że ? Nie wydaje mi się to oczywiste i właśnie o to chodzi!

n^{t h}

$n^{th}$

n

$n$

R B_{n}

$RB_n$

μ_{n} \to 0

$\mu_n \to 0$

— Aryabhata

Wcześniejsza wersja tego pytania twierdziła, że środowisko uruchomieniowe algorytmu rekurencyjnego na czerwono-czarnym drzewie, które wykonuje liniową ilość pracy na każdym etapie, niekoniecznie jest

. To twierdzenie było nieprawidłowe; równowaga wysokości oznacza, że głębokość

węzłowego drzewa czerwono-czarnego wynosi

. Zatem jeśli wykonujesz pracę

na każdym poziomie drzewa, całkowita praca to

O (n \log n)

$O(n\log n)$

n

$n$

O (\log n)

$O(\log n)$

O (n)

$O(n)$

O (n \log n)

$O(n \log n)$

— JeffE

Twierdzenie : Czerwono-czarne drzewa można dowolnie niezrównoważić $\mu$ .

Pomysł na dowód : wypełnij prawą poddrzewę jak największą liczbą węzłów, a lewą jak najmniejszą liczbą węzłów dla danej liczby $k$ czarnych węzłów na każdej ścieżce liścia.

Dowód : Określanie sekwencji $T_k$ z czarnymi drzewa tak, $T_k$ ma $k$ czarne węzłów każdej ścieżki od korzenia do dowolnego (wirtualnego) liści. Zdefiniuj $T_k = B(L_k, R_k)$ przy pomocy

$R_k$ pełne drzewo o wysokości $2k - 1$ z pierwszym, trzecim, ... poziomym kolorem czerwonym, pozostałe czarne i
$L_k$ pełne drzewo wysokości $k-1$ ze wszystkimi węzłami w kolorze czarnym.