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$ $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 . $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 ? $O(\log n)$ $\omega(\log n)$

graph-theory tree

— Marc Bury
źródło

@Marc: Litera (5. linia) pochodzi oczywiście od `` zbyt wielu węzłów w '' (7. linia)?

T

$T$

— Oleksandr Bondarenko

@Marc: Czy mógłbyś, bardziej precyzyjnie, stwierdzić, że „dwie ścieżki są różne, jeśli używają różnych węzłów potomnych w węźle rozgałęziającym”. Masz na myśli, że są różne, jeśli istnieje taki rozgałęziony węzeł, w którym używają różnych węzłów potomnych?

— Oleksandr Bondarenko

Edytuję pytanie i staram się je uściślić.

— Marc Bury,

Co o drzewie, które ma tylko jedną ścieżkę (a węzłów)? Czy to jest dozwolone?

n

$n$

— Peter Shor,

To dobre pytanie. Jest to dozwolone, ale nie jest to interesujący przypadek :) Następnie powinniśmy ustalić dolną granicę liczby rozgałęzień w drzewie, np. .

ω (\log n)

$\omega(\log n)$

— Marc Bury,

Dolna granica to ścieżki z węzłami rozgałęziającymi , jeśli masz w drzewie przynajmniej węzły rozgałęziające . $\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^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$ $\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 . $2^{-k}$ $1$ $1-\frac{1}{n}$ $\log_2 n$ $\Omega(\log n)$ $O(\log n)$

— Peter Shor
źródło

Jeśli ktoś zastanawia się, dlaczego nazywam równanie nierównością, nierówność Krafta ma znak równości dla kompletnych drzew binarnych.

— Peter Shor,

Dziękuję za tę miłą odpowiedź. Do tej pory nie znałem nierówności Krafta. Bardzo przydatna nierówność.

— Marc Bury,