Udowodnienie, że plik binarny ma

Próbuję udowodnić, że sterty binarne z węzłami mają dokładnie liści, biorąc pod uwagę, że stertę buduje się w następujący sposób: $n$ $\left\lceil \frac{n}{2} \right\rceil$

Każdy nowy węzeł jest wstawiany przez przeskalowanie w górę . Oznacza to, że każdy nowy węzeł musi zostać utworzony przy następnym dostępnym podrzędnym. Rozumiem przez to, że dzieci są napełnione niżej i od lewej do prawej. Na przykład następująca sterta:

    0
   / \
  1   2

będzie mieć zostały zbudowane w tej kolejności: 0, 1, 2. (Liczby są tylko indeksy, dają żadnych wskazówek rzeczywistych danych przechowywanych w tym węźle).

Ma to dwie ważne implikacje:

Nie może istnieć węzeł na poziomie bez poziomu całkowicie wypełnionego $k+1$ $k$
Ponieważ dzieci są budowane od lewej do prawej, między węzłami na poziomie nie może być „pustych przestrzeni” ani takich sytuacji: $k+1$
```
    0
   / \
  1   2
 / \   \
3  4    6
```

(Z mojej definicji byłby to nielegalny stos). Zatem dobrym sposobem na myślenie o tym stosie jest implementacja tablicy w stosie, w której nie może być żadnych „skoków” w niezdecydowaniu tablicy.

Pomyślałem więc, że indukcja byłaby prawdopodobnie dobrym sposobem na zrobienie tego ... Być może coś, co dotyczy nawet dziwnych przypadków dla n. Na przykład niektóre indukcje wykorzystujące fakt, że nawet hałdy zbudowane w ten sposób muszą mieć wewnętrzny węzeł z jednym dzieckiem dla parzystego n, a nie takie węzły dla nieparzystego n. Pomysły?

data-structures binary-trees

— varatis
źródło

@DaveClarke: Niezupełnie; powiązane pytanie jest wynikiem nieporozumienia na temat pozostawionych nam części redaktorów w celach informacyjnych.

— Raphael

Czy próbowałeś indukcji przez numer węzła lub. liczba wstawek?

— Raphael

@DaveClarke: Dlaczego? To samo w sobie ważne pytanie, imho.

— Raphael

BTW, pytanie nie ma nic wspólnego ze stertami. Roszczenie dotyczy dowolnego pełnego drzewa binarnego

— Ran G.

Odpowiedzi:

Jeśli poprawnie otrzymam twoje pytanie, otrzymana sterta jest po prostu uporządkowanym drzewem binarnym, gdzie w porządku oznacza, że poziom można zająć dopiero po całkowitym wypełnieniu poziomu , a każdy poziom zajmuje od lewej w prawo, bez pomijania. $k$ $k-1$

Potem dowód idzie w ten sposób.

Idealne drzewo głębokości ma dokładnie węzłów. $k$ $2^{k+1}-1$
Załóżmy, że hałda osiąga głębokość . A zatem
1. do poziomu drzewo jest idealne (i ma węzłów) $k-1$ $2^k-1$
2. na ostatnim poziomie są dokładnie węzłów, z których wszystkie są liśćmi. $n-2^k+1$
Każdy liść na tym poziomie ma rodzica. Co więcej, każde dwa kolejne liście mają tego samego ojca (może poza ostatnim węzłem, którego ojciec ma tylko jedno dziecko) $k$
Zatem z węzłów na poziomie , $2^{k-1}$ $k-1$ to rodzice, a reszta $\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$ to liście. $2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
Całkowita ilość liści wynosi Co daje ci to, czego potrzebujesz. $n - 2^{k} + 1 + 2^{k - 1} - ⌈ \frac{n - 2^{k} + 1}{2} ⌉$ $n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$

— Ran G.
źródło

Zauważ, że pełne różnią się od kompletnych różnią się od doskonałych drzew binarnych. Niefortunny, dwuznaczny i niespójny wybór słów, ale co możesz z tym zrobić. Wydaje mi się, że trzymanie się definicji Wikipedii ma sens, ponieważ większość najpierw tam zajrzy?

— Raphael

Och, wow, nawet nie znałem tych warunków. Dzięki za zwrócenie na to uwagi.

— Ran G.

„aż do poziomu k-1 drzewo jest idealne (i ma tam 2 ^ k - 1 węzłów)” i „Zatem z 2 ^ (k-1) węzłów na poziomie k-1” wydaje się być sprzecznymi stwierdzeniami, czy coś mi brakuje?

— adrian h.

2^{k} - 1

$2^k-1$

2^{k - 1}

$2^{k-1}$

2^{k - 1} + 2^{k - 2} + . . .

$2^{k-1}+2^{k-2}+...$

Ach, masz całkowitą rację, wielkie dzięki za wyjaśnienie!

— adrian h.

Oto prostszy logiczny dowód.

$n^{th}$ $\lfloor{n/2}\rfloor$ $\lfloor n/2 +1\rfloor)^{th}$ $\lfloor{n/2}\rfloor$

$\lfloor(n/2)\rfloor$ $\lceil(n/2)\rceil$

— Zubin Pahuja
źródło

Dość intuicyjne i jasne wyjaśnienie. Dzięki.

— whitehat