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ększa4 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.