Temat 5

Question 1

Czym jest słownik?

Answer 1

ADT przechowujące elementy w postaci pary klucz-wartość.

Question 2

Czym jest BST? Jakie dwie ważne metody zawiera? Jaka jest jego złożoność średnia?

Answer 2

Binarne drzewo poszukiwań to drzewo, gdzie klucz węzła jest większy niż klucz lewego syna i mniejszy niż klucz prawego syna.

Zawiera metody rotacyjne.

Średnio: O(log n)

Question 3

Jakie są właściwości drzewa AVL?

Answer 3

Każdy wierzchołek przechowuje współczynnik zrównoważenia (różnica wysokości lewego i prawego poddrzewa).

Wartości -1, 0, 1 są akceptowalne. Wartości -2, 2 wymagają naprawy drzewa

Question 4

Ile jest potrzebnych rotacji, aby naprawić drzewo AVL?

Answer 4

Jedna lub dwie rotacje po każdej zmianie struktury.

Question 5

Na czym polega równoważenie za pomocą algorytmu DSW?

Answer 5

Najpierw prawa rotacja na każdym węźle w drzewie, tworząc listę.

Zmniejszenie wysokości drzewa. Dla każdego drugiego węzła w liście, wykonujemy rotację w lewo, aż drzewo będzie zrównoważone.

Question 6

Różnice w wykorzystaniu drzew AVL, a drzew Czerwono-Czarnych.

Answer 6

AVL:
- Wykorzystujemy do metody find(), gwarantuje nam to lepszą wydajność.

Czerwono-Czarne:
- Daje nam lepszą wydajność dla metod: insert() i delete().

Question 7

Czy operacje rotacji w drzewach binarnych są zawsze korzystne?

Answer 7

Rotacje mogą poprawić równoważenie drzewa, ale dodają tym samym dodatkową złożoność.