Dolna granica liczby „krótkich” ścieżek w zrootowanym drzewie o wielomianowym rozmiarze

Niech będzie zrootowanym drzewem binarnym. Każda ścieżka od nasady do liścia ma długość . Każdy węzeł ma zawsze lewy i prawy węzeł potomny, ale możliwe jest, że są one takie same (więc zawsze możliwe są ścieżki). Rozmiar jest ograniczony przez . Węzeł z różnymi węzłami potomnymi nazywa się węzłem rozgałęziającym .T n T 2 n T O ( p o l y ( n ) $T$$T$$n$$T$$2^n$$T$$O(poly(n))$

Mówimy, że dwie ścieżki są różne, jeśli istnieje jeden wspólny rozgałęziony węzeł, a jedna ścieżka prowadzi do lewego węzła potomnego, a druga ścieżka do prawego węzła potomnego. Oczywiste jest, że istnieje co najmniej jedna ścieżka w z rozgałęzieniami . W przeciwnym razie w byłoby za dużo węzłów .O ( log n ) $T$$O(\log n)$$T$

Czy istnieje lepsza dolna granica liczby ścieżek z gałęziami rozgałęziającymi jeśli wiem, że w drzewie są rozgałęzienia ?ω ( log n $O(\log n)$$\omega(\log n)$

Dolna granica to ścieżki z węzłami rozgałęziającymi , jeśli masz w drzewie przynajmniej węzły rozgałęziające .O ( log n ) Ω ( log n $\Omega(\log n)$$O(\log n)$$\Omega(\log n)$

Można to osiągnąć: użyj drzewa, które ma jedną długą ścieżkę (długość ), z których wszystkie są węzłami rozgałęziającymi, bez żadnych innych węzłów rozgałęziających w drzewie.$n$

Oto szkic dolnej granicy.

Po pierwsze, kompaktuj drzewo, zwężając dowolny węzeł wewnętrzny, który nie jest węzłem rozgałęziającym. Jeśli pierwotny rozmiar drzewa wynosił , nowe drzewo musi nadal mieć wartość , ponieważ ograniczyłeś tylko liczbę węzłów. Głębokość liścia to liczba rozgałęzionych węzłów na oryginalnej ścieżce do tego liścia, a my mamy pełne drzewo binarne (każdy węzeł ma stopień 2 lub 0). < n $< n^c$$< n^c$

Jeśli nie ma liści głębokości , wówczas liczba ścieżek jest o jeden większa niż liczba rozgałęzionych węzłów, czyli , więc możemy założyć, że co najmniej jeden liść ma głębokość .$\Omega(\log n)$$\Omega(\log n)$$\Omega(\log n)$

Następnie przypomnij sobie nierówność Krafta. Jeśli głębokość liścia w pełnym drzewie binarnym wynosi , to .$d(v)$$\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$

Teraz mamy mniej niż liści. Chcemy pokazać, że mamy ich dużo na głębokości . Załóżmy, że eliminujemy z analizy te, które mają głębokość co najmniej . Usuwa to co najwyżej wagę z sumy nierówności Krafta, więc dla tych liści na głębokości co najwyżej mamy . Mamy także (ponieważ co najmniej jeden liść ma zbyt dużą głębokość, aby można go było uwzględnić w tej sumie).$n^c$$O(\log n)$$\log_2(n^{c+1}) = (c+1) \log_2 n$$1/n$$v$$d(v)\leq (c+1) \log_2 n$ ∑vlowdepthleaf2-d(v)<$\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$$\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$

Dość łatwo jest wykazać, że aby uzyskać sumę liczb ściśle między a , potrzebujemy co najmniej z nich. To pokazuje, że istnieją ścieżki z węzłami rozgałęziającymi . 1 1 - $2^{-k}$$1$ log2nΩ(logn)O(logn$1-\frac{1}{n}$$\log_2 n$$\Omega(\log n)$$O(\log n)$