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

10

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 ) )TTnT2nTO(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 ) TTO(logn)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(logn)ω(logn)

Marc Bury
źródło
@Marc: Litera (5. linia) pochodzi oczywiście od `` zbyt wielu węzłów w '' (7. linia)?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
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. . ω(logn)
Marc Bury,

Odpowiedzi:

9

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 )Ω(logn)O(logn)Ω(logn)

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<nc<nc

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ść .Ω(logn)Ω(logn)Ω(logn)

Następnie przypomnij sobie nierówność Krafta. Jeśli głębokość liścia w pełnym drzewie binarnym wynosi , to .d(v)Σv leaf2d(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).ncO(logn)log2(nc+1)=(c+1)log2n1/nvd(v)(c+1)log2nvlowdepthleaf2-d(v)<1v low depth leaf2d(v)>11nv low depth leaf2d(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 - 12k1 log2nΩ(logn)O(logn)11nlog2nΩ(logn)O(logn)

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,