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:

1. Nie może istnieć węzeł na poziomie bez poziomu k całkowicie wypełnionego$k+1$$k$

2. 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?

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 k - 1 , a każdy poziom zajmuje od lewej w prawo, bez pomijania.$k$$k-1$

Potem dowód idzie w ten sposób.

1. Idealne drzewo głębokości ma dokładnie 2 k + 1 - 1 węzłów.$k$$2^{k+1}-1$
2. Załóżmy, że hałda osiąga głębokość . A zatem $k$
   1. do poziomu drzewo jest idealne (i ma 2 k - 1 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$
3. 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$
4. Zatem z węzłów na poziomie k - 1 , ⌈ n - 2 k + $2^{k-1}$$k-1$to rodzice, a reszta2k-1-⌈n-2 k +$\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$
5. Całkowita ilość liści wynosi Co daje ci to, czego potrzebujesz. $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$

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$