ASD Ćwiczenia 7

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