ASD Ćwiczenia 7: Różnice pomiędzy wersjami

Wersja z 10:43, 29 wrz 2006

Podaj metodę przygotowywania zrównoważonego drzewa BST (o wysokość $O (\log n)$ ) dla zadanego zbioru kluczy $a_{1}, \dots, 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, \dots, y]$ ?

Wersja z 15:26, 19 wrz 2006 pokaż źródło Dorota (dyskusja \| edycje) 376 edycji Nie podano opisu zmian ← poprzednia edycja		Wersja z 10:43, 29 wrz 2006 pokaż źródło Walen (dyskusja \| edycje) 177 edycji Nie podano opisu zmian następna edycja →
Linia 1:		Linia 1:
	# Podaj metodę przygotowywania zrównoważonego drzewa BST (o wysokość <math>O(\log n)</math>) dla zadanego zbioru kluczy <math>a_1,\ldots,a_n</math>.		# Podaj metodę przygotowywania zrównoważonego drzewa BST (o wysokość <math>O(\log n)</math>) dla zadanego zbioru kluczy <math>a_1,\ldots,a_n</math>.
	# ~~Jak poprawić~~ operację ~~usuwania~~ elementów z ~~drzewa BST tak, by pesymistyczny koszt wynosił~~ <math>~~O(1)~~</math>?		# 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 <math>[x,\ldots,y]</math>?