Wejściówka 6     AVL

 

 

  1. Dopisz wagi przy każdym z wierzchołków podanego drzewa.
                      x
            x                        x
        x                       x       x
                                        x    x

 

  1. Jaki jest koszt usunięcia jednego elementu z drzewa AVL, które zawiera  już k wierzchołków.
  2. Czy następujący ciąg może być ciągiem elementów odczytanych z drzewa AVL w porządku prefiksowym? (Jeśli tak – narysuj to drzewo, jeśli nie napisz dlaczego.)
    8,5,3,2,1,4,6,7,10,9,11,12.

 

  1. Narysuj minimalne drzewo AVL o wysokości 3.
  2. Jaki jest koszt włożenia jednego elementu do drzewa AVL, którego wysokość wynosi h?
  3. Narysuj drzewo otrzymane w wyniku włożenia elementu 3,5 do podanego drzewa.
           6
       2      8
    1   4   7   9
        3  5

  4.  Jaka jest największa możliwa wysokość drzewa AVL, które  ma  12 wierzchołków?
  5. Jaki będzie efekt usunięcia elementu 10 z następującego drzewa AVL?
  6. Ile co najwyżej rotacji trzeba wykonać przy wkładaniu jednego elementu do drzewa AVL o n wierzchołkach?

             10

    6      12
5    8         13
   7