MOKIP 25.04.2012

Co to jest drzewo poszukiwań binarnych?

1. Operacje na drzewie
   • Find
   • Insert
   • Delete
   • Maximum
   • Minimum
   • Successor
   • Predecessor
2. Sposób implementacji
3. Korzystamy z gotowca, czyli std::set…
4. Ale nie zawsze - o wyznaczaniu statysyk pozycyjnych (n-ty najmniejszy element w zbiorze)
5. Rodzaje drzew zrółnoważonych
   • AVL
   • RBBST (czerwono-czarne)
   • Splay
   • Drzewiec (Treap)

Drzewiec = drzewo poszukiwań binarnych + kopiec

1. Sposób implementacji - wprowadzamy losowy priorytet
2. Jak utrzymać własność kopca - funkcje left-rotate i right-rotate
3. Wytłumaczenie + kod
4. Zadanie Rotacje na drzewie z II etapu XVIII OI. Można użyć drzewa zrównoważonego. Wskazówka - idziemy od liści i zawsze wstawiamy elementy z mniejszego drzewa do większego, aktualizując przy tym wynik.

Garstka ciekawostek

1. Kiedy nie obchodzi nas kolejność - tr1/unordered_set
2. Problem znajdowania czwórki elementów o zadanej sumie w oczekiwanym czasie $O(n^2)$ (z użyciem unordered_set)
3. Dlaczego nie należy haszować modulo long long - dowód.