ALG8

138 Rozdział 5. Struktury danych

• „prawy” potomek /-tego węzła jest „schowany” pod indeksem 2*i+l. Uwaga: dany węzeł może mieć od 0 do 2 potomków.

Powyżej zdefiniowaliśmy sposób składowania danych, nic jednak nie powiedzieliśmy o zależnościach istniejących pomiędzy nimi. Otóż cechą charakterystyczną sterty jest to, iż wartość każdego węzła jest większa⁴ od wartości węzłów jego dwóch potomków - jeśli oczywiście istnieją. Sposób organizacji drzewa (jak również w konsekwencji tablicy) ułatwia operacje wstawiania i usuwania elementów. Możemy bowiem nowy element bez problemu „dopisać” na koniec tablicy (co oczywiście zburzy nam lad wcześniej tam panujący), następnie za pomocą dość prostych modyfikacji tablicy przywrócić z powrotem tablicy (drzewu) własności sterty. Popatrzmy na przykładzie, w jaki sposób jest konstruowana sterta ze zbioru elementów: 37, 41, 26, 14, 19, 99, 23, 17, 12, 20, 25 i 42 - dołączanych sukcesywnie do drzewa. Cały proces jest pokazany na rysunku 5 - 19.

Rys. 5-19.

Konstrukcja sterty na przykładzie.

1	6	9	11
37	99	99	99
2	A	A	A
	37 41	37 41	37 41
I	/X /	/\ z\	/ \ /\
31	14 19 26	17 192673	17 2526 23
		/ \	^ \ /A
3 41	i	14 12	14 12 19 20
A	A
17
	37 41
	/\ /\
4 41
	14 192623
A		10	12
37 26
	8	99	99
14	99	A	/ \
	A	27 4 1	37 42
	37 41	/ \ /A	/A /A
A	/\ /\	11 20 26 23	11 25 41 23
37 26	17 192G23	/ A /	/ \ /A /
/\	/	14 1219	14 12 192026
14 19	14

Na rysunku tym widzimy gdzie wędruje nowy - zaznaczony wytłuszczoną czcionką - element. Poprzez porównanie z etapem poprzednim łatwo zauważamy modyfikacje struktury drzewa. Załóżmy, że dokładamy na koniec drzewa

Spotyka się również implementacje, w których jest to wartość nie większa.

ALG8

ALG8

ALG8

ALG8