Ćwiczenia
czw., 10/14/2010 - 11:23 — Mirek Rachelski
- Podaj metodę przygotowywania zrównoważonego drzewa BST (o wysokość \( O(\log n) \)) dla zadanego zbioru kluczy \( a_1,\ldots,a_n \).
- W jaki sposób efektywnie dodać do drzew BST operację LiczbaElementówzZakresu(x,y) zwracającą liczbę elementów drzewa o wartościach z zakresu \( [x,\ldots,y] \)?
- Ile jest różnych drzew BST zawierających klucze \( 1,\ldots,n \)?
- W jaki sposób można wykorzystać drzewa BST do sortowania ciągu liczb?