Lekcja_06 - drzewa binarnych poszukiwań1. BST2. AVLWyjścieDrzewa binarnych poszukiwańCzy każda ścieżka od korzenia do liścia w drzewie BST jest uporządkowana malejąco?TAKNiePrzykłady drzew binarnychKtóre z drzew na powyższym rysunku jest drzewem binarnych poszukiwań?AB C1. (1p) Wszystkie etykiety wierzchołków dowolnego poziomu w drzewie BST, czytane od lewej do prawej tworzą ciąg rosnący. Prawda czy fałsz?prawdafałszZastanów się! Ile co najwyżej wierzchołków wewnętrznych i ile co najwyżej liści może posiadać drzewo binarne o wysokości 3?2. (1p) Ile jest liści w pełnym drzewie binarnym o wysokości h?co najwyżej hdokładnie h^2dokładnie 2^hco najmniej 2^(h+1)3. (1p) Etykietami pewnego drzewa binarnych poszukiwań są liczby naturalne 1,2,... 100. Jaką etykietę ma korzeń tego drzewa, jeżeli wszystkie elementy, z wyjątkiem dziesięciu należą do prawego poddrzewa? Nie można tego ustalić jednoznacznie.10011Każda z liczb 1-100 może być etykietą korzenia.Zastanów się! Czy ksztalt drzewa BST zależy od kolejności wstawiania elementów?4.(1p) Jaka jest maksymalna długość ścieżki w drzewie BST o n wierzchołkach?O(lg n)n-1n/25. (1p) Jaki jest koszt(mierzony liczbą wykonanych porównań) wstawienia n elementów do początkowo pustego drzewa BST, jeśli wiadomo, że wstawiane elementy tworzą ciąg malejący?O(lg n)n-1Theta(n^2)nPytanie: Rozważmy drzewo B. Jaki będzie porządek etykiet tego drzewa, jeśli je odczytamy metodą inorder?6. (1p) W jakim porządku należy przeczytać etykiety drzewa BST tak by utworzyły ciąg uporządkowany rosnąco? postorderpreorderinorder7. (1p) Wymień wszystkie liście drzewa BST utworzonego przez kolejne wstawianie elementów 5,1,8,6,3,2,7 do początkowo pustego drzewa.1,3,6,72,72,3,58. (1p) Jaki jest koszt, mierzony liczbą porównań elementów, usunięcia jednego elementu z drzewa BST o 127 wierzchołkach?rzędu 127 porównańokoło 100 porównańtylko jedno porównanieco najwyżej 7 porównańOdpowiedzi :  Wyniki