Treść zadania

Najlepsze rozwiązanie

• 

  3 0

  antekL1 25.12.2015 (09:25)

  Wykaż, że drzewo binarne o wysokości h ma co najmniej 2^h+1 węzłów.
  
  To twierdzenie byłoby bardziej prawdziwe w wersji "co najwyżej".
  Zobacz rysunek w załączniku i umówmy się na definicję "wysokości drzewa".
  Wysokość = ilość kresek od szczytu drzewa do najdalszego potomka"
  
  Wtedy bardzo zdegenerowane drzewko po lewej stronie ma wysokość 3
  (i tylko 4 węzły, zdecydowanie mniej niż 2^3 + 1 = 9)
  
  Kolejne (od lewej) już pełne drzewka mają:
  wysokość 0 ; 1 węzeł
  wysokość 1 ; 3 węzły
  (nie narysowane, ale popatrz na to drzewo po prawej stronie) wysokość 2 ; 7 węzłów
  wysokość 3 ; 15 węzłów
  ....
  itd.
  Zauważ, że każdy następny poziom zawiera [ co najwyżej ] 2 razy więcej węzłów
  niż poziom poprzedni. Ilości węzłów tworzą więc ciąg geometryczny:
  1, 2, 4, 8, 16..... Pierwszy wyraz a0 = 1; Iloraz q = 2.
  Ze szkolnego wzoru na sumę ciągu geometrycznego mamy:
  
  \mbox{suma}=\sum_{k=0}^{n}a_0q^{k}=a_0\frac{q^{n+1}-1}{q-1}=1\cdot\frac{2^{n+1}-1}{2-1}=2^{h+1}-1
  
  gdzie podstawiłem a0 i q jak wyżej i zamieniłem "n" na "h".
  
  Mamy teraz właściwe twierdzenie:
  "Ilość węzłów w drzewie o wysokości h jest nie większa niż 2^(h+1) - 1".
  
  Zobacz, że to się zgadza:
  wysokość = 0 ---> suma = 2^1 - 1 = 1
  wysokość = 1 ---> suma = 2^2 - 1 = 3
  wysokość = 2 ---> suma = 2^3 - 1 = 7
  wysokość = 3 ---> suma = 2^4 - 1 = 15
  ....
  ================================
  
  Dwie uwagi:
  1) Jeżeli wysokość drzewa określimy inaczej - jako ilość poziomów
  (czyli wysokości drzew na rysunku to 4, 1, 2, 4)
  wtedy zamiast 2^(h+1) - 1 trzeba napisać 2^h - 1
  
  2) Jeżeli porównanie z sumą ciągu geometrycznego nie wystarczy jako dowód
  to udowodnijmy ten wzór indukcyjnie:
  Dla n = 0 mamy 2^(0+1) - 1 = 2 - 1 = 1. Zgadza się.
  Zakładamy prawdziwość wzoru dla "n"
  i stawiamy tezę, że jest on prawdziwy na n+1,
  czyli suma Sn pierwszych n wyrazów spełnia taki warunek:
  
  \mbox{Jezeli}\qquad S_n=2^{n+1}-1\qquad\mbox{to}\qquad S_{n+1}=2^{n+2}-1
  
  Zauważ, że w każdym kolejnym poziomie dokładamy 2^(n+1) węzłów czyli:
  
  S_{n+1}=S_n + 2^{n+1}=2^{n+1}-1+2^{n+1}=2\cdot 2^{n+1}-1=2^{n+2}-1
  
  i mamy udowodnione nasze twierdzenie.
  ====================================
  
  W razie pytań pisz proszę na priv.
  Wesołych Świąt!
  Antek

  Załączniki

  • drzewa.pdf (62 KB)

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie