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ść0 ≤ μ ≤ $\mu$$0 \le \mu \leq \frac{1}{2}$$N$

$$\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).| N L | N | N | $\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.μ μ > 0 O ( log n $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$

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.

Oczywiście, wszystkie $T_k$ są czerwono-czarny drzewa.

$T_1$$T_2$$T_3$

^{[ źródło ]}

^{[ źródło ]}

^{[ źródło ]}

Teraz zweryfikujmy wrażenie, że prawa strona jest ogromna w porównaniu do lewej. Nie będę liczyć wirtualnych liści; nie wpływają na wynik.

$T_k$$k-1$$2^k - 1$$2k - 1$$2^{2k}-1$$\mu$

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

$\mu > 0$

Nie. Weź pod uwagę czerwono-czarne drzewo o następującej specjalnej strukturze.

• $d$
• $2d$

$2^{2d+1}-1$$2^{d+1}-1$