Temat 16: Struktury danych (II)

Wstecz; Ostatnia modyfikacja: 27.04.2015

---

• Ćwiczenie 1 (dokończenie): implementacja drzew BST - wstawianie elementu, wypisywanie drzewa, wyszukiwanie elementu.
• Ćwiczenie 2: wykorzystując implementację drzew BST zaimplementuj słownik (przechowujemy pary (key, value)). Zaimplementuj metodę __setitem__(self, k,v)
• Zbalansowane drzewa binarne (AVL, czerwono-czarne)
• Implementacja drzew AVL w Pythonie
• Alternatywa dla drzew zbalansowanych: drzewa splay.
• Oczekiwany czas wyszukiwania w losowym drzewie BST na podstawie losowej permutacji to $O(logn)$.

operacja	Sorted lists	Drzewa BST	Zrównoważone drzewa BST	Tablice hashujące
put	$O(n)$	$O(n)$	$O(logn)$	$O(1)$*
get	$O(log(n))$	$O(n)$	$O(logn)$	$O(1)$*
in	$O(log(n))$	$O(n)$	$O(logn)$	$O(1)$*
del	$O(n)$	$O(n)$	$O(logn)$	$O(1)$*

* - koszt oczekiwany, dla pozostałych koszt pesymistyczny
• Kod z ćwiczeń