2. Operacja wstawiania.

Niech Heap oznacza zbiór kopców etykietowanych elementami zbioru Et. Operacja wstawiania insert ma następującą sygnaturę:

insert : Et ´ Heap ® Heap.

Tak, jak w przypadku struktur drzewiastych BST I AVL, wymagamy, aby operacja insert spełniała dla dowolnych eÎEt i HÎHeap, specyfikację:

insert(e,H) Î Heap

(member(e,H) ® H = insert(e,H)) Ù (Ø member(e,H) ® member(e,insert(e,H))),

gdzie member jest relacją zachodzącą między elementem i kopcem odpowiadającą na pytanie, czy element należy, czy nie należy do kopca.

Idea algorytmu wstawiania elementu e do kopca H polega na tym, by zachować strukturę drzewa doskonałego kosztem uporządkowania. Odtworzenie tej struktury jest dużo trudniejsze, gdyż dotyczy całego drzewa, niż poprawienie etykietowania, które dotyczy tylko jednej ścieżki. Jeśli zapomnimy na chwilę o uporządkowaniu drzewa, to naturalnym miejscem, do którego możemy dowiązać nowy wierzchołek jest pierwszy niekompletny węzeł na przedostatnim poziomie drzewa, o ile taki istnieje, i pierwszy z lewej liść, w przeciwnym przypadku (por. rysunek 9.1(a)).

Metoda.

Dowiąż nowy wierzchołek x do pierwszego z lewej wierzchołka, którego rząd jest <2 na przedostatnim poziomie, gdy drzewo D nie jest pełne, i, na ostatnim poziomie, gdy jest pełne (por. rysunek 9.3).
Nadaj nowemu wierzchołkowi etykietę e.
Jeżeli tak otrzymane drzewo nie jest kopcem, to przesuwając się wzdłuż drogi od liścia x do korzenia drzewa, zamieniaj etykiety ojca i syna, o ile nie spełniają warunku częściowego uporządkowania kopca.

Przykład 2.1

Na rysunku 9.3(a) przedstawiono przykład kopca o wysokości 3. Chcemy dołączyć do tego kopca etykietę 0. Pierwszy krok polega na dowiązaniu nowego wierzchołka z etykietą 0 jako prawego syna wierzchołka z etykietą 6. Jest to właśnie pierwszy z lewej wierzchołek na przedostatnim poziomie, który nie ma kompletu synów. W wyniku otrzymaliśmy drzewo doskonałe (por. rysunek 9.3(b), ale bez własności częściowego uporządkowania.

Stwierdzamy to porównując nowowstawiony element z etykietę jego ojca. Ponieważ 6>0, więc zamieniamy miejscami te etykiety. Jedna zamiana jednak nie wystarczy i musimy jeszcze zamienić 0 z 3 i 0 z 1, jak pokazano na rysunku 9.3(c). Ostatecznie otrzymamy kopiec przedstawiony na rysunku 9.3 (d). J

Koszt operacji wstawiania

Zgodnie z opisanym algorytmem, kroki 1-2 mają koszt stały. Poprawienie uporządkowania dotyczy tylko jednej ścieżki od nowowstawionego wierzchołka do korzenia (w najgorszym razie). Wynika stąd, że koszt operacji wstawiania można oszacować z góry przez wysokość drzewa. Zgodnie z lematem 1.2, jest on więc równy T(n) = O(lg n), dla drzewa o n wierzchołkach.

Uwaga. Implementacja przedstawionego algorytmu na drzewie sprawia trochę kłopotów. Po pierwsze, musimy w każdym węźle pamiętać referencję do wierzchołka ojca. Po drugie, musimy znaleźć wierzchołek, do którego należy dowiązać nowy element. Pamiętanie jednej referencji do tego wierzchołka nie wystarczy, bo po kolejnych wstawieniach trzeba ją uaktualnić. Natomiast pamiętanie w każdym węźle referencji do najbliższego "następnika" z prawej wymaga sporo dodatkowej pamięci. O implementacji algorytmu wstawiania będzie mowa w dalszej części wykładu.

Pytanie 2: Czy dla dowolnego kopca, ciąg etykiet wierzchołków wypisanych w porządku "wszerz" jest uporządkowany rosnąco?

« poprzedni punkt następny punkt »