Wejściówka 5 Struktury danych
Czy następujący ciąg liczb może być ciągiem etykiet drzewa BST odczytanym w porządku inorder (tzn.: lewy, korzeń, prawy): 1,4,6,8,9,3, 5. Odpowiedź uzasadnić.
Utwórz drzewo BST wkładając kolejno elementy 5, 1, 4, 8, 6, 3, 9, 2
do drzewa początkowo pustego.
Jaki jest koszt pesymistyczny wstawienia jednego elementu do BST o n wierzchołkach?
Wejściówka 5
Jaka jest wysokość drzewa binarnego, zawierającego 17 elementów? Podaj oszacowanie z góry i w dołu. Odpowiedź uzasadnić.
Do początkowo pustego drzewa BST włożono elementy 5,4,3,2,1,6,7,8. Narysuj drzewo otrzymane w wyniku.
Jaki jest koszt średni usunięcia jednego elementu z drzewa BST o n wierzchołkach?
Wejściówka 5
Czy z drzewie BST wszystkie wierzchołki leżące na tym samym poziomie tworzą ciąg uporządkowany? Odpowiedź uzasadnić.
Z drzewa BST postaci 4
3 7
1 2 5 8
6
usunięto korzeń . Narysuj drzewo BST powstające w wyniku tej operacji.
Jaki jest średni koszt wyszukania 1 elementu w drzewie BST o n wierzchołkach?
Czy wykonanie operacji włożenia elementu e do stosu, a potem usunięcia jednego elementu zależy od kolejności ich wykonywania? Odpowiedź uzasadnić.
Dany losowo ciąg najpierw wkładamy kolejno do drzewa BST a potem odczytujemy etykiety tego drzewa w porządku inorder. Jaki będzie porządek elementów na wyjściu i jaki jest koszt każdego etapu tego algorytmu mierzony liczbą wykonanych porównań?
Podaj przykład formuły prawdziwej w dowolnej strukturze stosów i fałszywej w strukturze kolejek FIFO.
Która wartość jest większa w drzewie doskonałym: liczba liści czy liczba wierzchołków wewnętrznych?