Ćwiczenia

1. Podaj metodę przygotowywania zrównoważonego drzewa BST (o wysokość \( O(\log n) \)) dla zadanego zbioru kluczy \( a_1,\ldots,a_n \).
2. 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] \)?
3. Ile jest różnych drzew BST zawierających klucze \( 1,\ldots,n \)?
4. W jaki sposób można wykorzystać drzewa BST do sortowania ciągu liczb?