ASD Ćwiczenia 7

From Studia Informatyczne

  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?