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.