Informatyka dla klas II

Sortowanie przez kopcowanie

Drzewo binarne

Dotychczas operowaliśmy na prostych strukturach danych, takich jak tablice. W tablicy elementy ułożone są zgodnie z ich numeracją, czyli indeksami. Jeśli za punkt odniesienia weźmiemy element d[i] (i = 2,3,..,n-1; n - liczba elementów w tablicy), to elementem poprzedzającym go będzie element o mniejszym o 1 indeksie, czyli d[i - 1]. Elementem następnym będzie element o indeksie o 1 większym, czyli d[i + 1]. Jest to tzw. hierarchia liniowa - elementy następują jeden za drugim. Graficznie możemy przedstawić to tak:

 

 

Pierwszy element d[0] nie posiada poprzednika (ang. predecessor - elementu poprzedzającego w ciągu). Ostatni element d[n-1] nie posiada następnika (ang. successor - elementu następnego w ciągu). Wszystkie pozostałe elementy posiadają poprzedniki i następniki.

Drzewo binarne jest hierarchiczną strukturą danych, którego elementy będziemy nazywali węzłami (ang. node) lub wierzchołkami. W hierarchii liniowej każdy element może posiadać co najwyżej jeden następnik. W drzewie binarnym każdy węzeł może posiadać dwa następniki (stąd pochodzi nazwa drzewa - binarny = dwójkowy, zawierający dwa elementy), które nazwiemy potomkami. dziećmi lub węzłami potomnymi danego węzła (ang. child node).

pic

Węzły są połączone krawędziami symbolizującymi następstwo kolejnych elementów w strukturze drzewa binarnego. Według rysunku po prawej stronie węzeł A posiada dwa węzły potomne: B i C. Węzeł B nosi nazwę lewego potomka (ang. left child node), a węzeł C nosi nazwę prawego potomka (ang. right child node).

Z kolei węzeł B posiada węzły potomne D i E, a węzeł C ma węzły potomne F i G. Jeśli dany węzeł nie posiada dalszych węzłów potomnych, to jest w strukturze drzewa binarnego węzłem terminalnym. Taki węzeł nosi nazwę liścia (ang. leaf node). Na naszym rysunku liśćmi są węzły terminalne D, E, F i G.

Rodzicem, przodkiem (ang. parent node) lub węzłem nadrzędnym będziemy nazywać węzeł leżący na wyższym poziomie hierarchii drzewa binarnego. Dla węzłów B I C węzłem nadrzędnym jest węzeł A. Podobnie dla węzłów D i E węzłem nadrzędnym będzie węzeł B, a dla F i G będzie to węzeł C.

Węzeł nie posiadający rodzica nazywamy korzeniem drzewa binarnego (ang. root node). W naszym przykładzie korzeniem jest węzeł A. Każde drzewo binarne, które zawiera węzły posiada dokładnie jeden korzeń.

 

Odwzorowanie drzewa binarnego

Jeśli chcemy przetwarzać za pomocą komputera struktury drzew binarnych, to musimy zastanowić się nad sposobem reprezentacji takich struktur w pamięci. Najprostszym rozwiązaniem jest zastosowanie zwykłej tablicy n elementowej. Każdy element tej tablicy będzie reprezentował jeden węzeł drzewa binarnego. Pozostaje nam jedynie określenie związku pomiędzy indeksami elementów w tablicy a położeniem tych elementów w strukturze drzewa binarnego.

Zastosujmy następujące odwzorowanie:

  • Element d[0] będzie zawsze korzeniem drzewa.
  • i-ty poziom drzewa binarnego wymaga 2i-1 węzłów. Będziemy je kolejno pobierać z tablicy.

Otrzymamy w ten sposób następujące odwzorowanie elementów tablicy w drzewo binarne:

 

pic

 

Dla węzła k-tego wyprowadzamy następujące wzory:

 

pic węzły potomne mają indeksy równe:
2k + 1 - lewy potomek
2k + 2 -
prawy potomek

węzeł nadrzędny ma indeks równy [(k - 1) / 2] (dzielenie całkowitoliczbowe)

 

Sprawdź, iż podane wzory są również spełnione w drzewach binarnych o większych rozmiarach niż prezentuje nasz przykład (pomocna może być kartka papieru).

 

Przykład:

Skonstruować drzewo binarne z elementów zbioru {7 5 9 2 4 6 1}

 

Operacja Opis
pic
7 5 9 2 4 6 1
Konstrukcję drzewa binarnego rozpoczynamy od korzenia, który jest pierwszym elementem zbioru, czyli liczbą 7.
pic
7 5 9 2 4 6 1
Do korzenia dołączamy dwa węzły potomne, które leżą obok w zbiorze. Są to dwa kolejne elementy, 5 i 9.
pic
7 5 9 2 4 6 1
Do lewego węzła potomnego (5) dołączamy jego węzły potomne. Są to kolejne liczby w zbiorze, czyli 2 i 4.
pic
7 5 9 2 4 6 1
Pozostaje nam dołączyć do prawego węzła ostatnie dwa elementy zbioru, czyli liczby 6 i 1. Drzewo jest kompletne.

 

Zrównoważone drzewa binarne

Umówmy się na potrzeby tego artykułu, iż binarne drzewo jest zrównoważone i uporządkowane, jeśli na wszystkich poziomach za wyjątkiem ostatniego posiada maksymalną liczbę węzłów, a na poziomie ostatnim węzły są ułożone kolejno od lewej strony. Innymi słowy, jeśli ostatni węzeł drzewa binarnego posiada numer i-ty, to drzewo zawiera wszystkie węzły od numeru 1 do i.

Warunek ten gwarantuje nam, iż każdy element tablicy będzie reprezentował pewien węzeł w drzewie binarnym - czyli w tej strukturze nie wystąpią dziury.

 

 

Drzewo po lewej stronie nie posiada węzła d[6]. Ale posiada wszystkie węzły od d[0] do d[5], jest zatem zrównoważone i uporządkowane. Można je bez problemu przedstawić za pomocą tablicy elementów od d[0] do d[5].

Drzewo po prawej stronie nie posiada węzła d[5]. Takiego drzewa nie przedstawimy poprawnie za pomocą tablicy elementów od d[0] do d[6], ponieważ nie mamy możliwości zaznaczenia (bez dodatkowych zabiegów), iż element d[5] nie należy do struktury drzewa. Zatem nie będzie to uporządkowane i zrównoważone drzewo binarne.

W uporządkowanych i zrównoważonych drzewach binarnych bardzo prosto można sprawdzić, czy k-ty węzeł jest liściem. Będzie tak, jeśli węzeł ten nie posiada węzłów potomnych. Zatem, jeśli drzewo binarne składa się z n węzłów, to wystarczy sprawdzić, czy 2k+1 > n-1. Jeśli tak, węzeł jest liściem. Jeśli nie, węzeł posiada potomka o indeksie 2k+1, zatem nie może być liściem.

 

Ścieżki na drzewach binarnych

Ścieżką nazwiemy ciąg węzłów drzewa binarnego spełniających warunek, iż każdy węzeł poprzedni jest rodzicem węzła następnego. Jeśli ścieżka składa się z k węzłów, to długością ścieżki jest liczba k - 1.

 

tree

 

Na powyższym rysunku zaznaczona została ścieżka biegnąca poprzez węzły {d[0], d[2], d[5], d[12]}. Ścieżka ta zawiera cztery węzły, ma zatem długość równą 3.

Wysokością drzewa binarnego nazwiemy długość najdłuższej ścieżki od korzenia do liścia. W powyższym przykładzie najdłuższa taka ścieżka ma długość 3, zatem zaprezentowane drzewo binarne ma wysokość równą 3.

Dla n węzłów zrównoważone drzewo binarne ma wysokość równą:

 

h = [log2n]

 

Podsumowanie nowej terminologii

węzeł  (ang. node)  -  element drzewa binarnego
rodzic, węzeł nadrzędny, przodek  (ang, parent node)  - węzeł leżący o 1 poziom wyżej w hierarchii
dziecko, potomek, węzeł potomny  (ang. child node)  - węzeł leżący o 1 poziom niżej w hierarchii, dla którego bieżący węzeł jest rodzicem.
korzeń drzewa  (ang. root node)  - pierwszy węzeł na najwyższym poziomie hierarchii, który nie posiada rodzica
liść, węzeł terminalny  (ang. leaf node)  - węzeł nie posiadający węzłów potomnych
ścieżka  (ang. path)  - droga na drzewie binarnym wiodąca poprzez poszczególne wierzchołki
 

Kopiec

Kopiec jest drzewem binarnym, w którym wszystkie węzły spełniają następujący warunek (zwany warunkiem kopca):

 

Węzeł nadrzędny jest większy lub równy węzłom potomnym (w porządku malejącym relacja jest odwrotna - mniejszy lub równy).

 

Konstrukcja kopca jest nieco bardziej skomplikowana od konstrukcji drzewa binarnego, ponieważ musimy dodatkowo troszczyć się o zachowanie warunku kopca. Zatem po każdym dołączeniu do kopca nowego węzła, sprawdzamy odpowiednie warunki i ewentualnie dokonujemy wymian węzłów na ścieżce wiodącej od dodanego węzła do korzenia.

 

Przykład:

Skonstruować kopiec z elementów zbioru {7 5 9 6 7 8 10}

Operacja Opis

7 5 9 6 7 8 10
Budowę kopca rozpoczynamy od pierwszego elementu zbioru, który staje się korzeniem.

7 5 9 6 7 8 10
Do korzenia dołączamy następny element. Warunek kopca jest zachowany.

7 5 9 6 7 8 10
Dodajemy kolejny element ze zbioru.
Po dodaniu elementu 9 warunek kopca przestaje być spełniony. Musimy go przywrócić. W tym celu za nowy węzeł nadrzędny wybieramy nowo dodany węzeł. Poprzedni węzeł nadrzędny wędruje w miejsce węzła dodanego - zamieniamy węzły 7 i 9 miejscami.
Po wymianie węzłów 7 i 9 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 6. Znów warunek kopca przestaje być spełniony - zamieniamy miejscami węzły 5 i 6.
Po wymianie węzłów 5 i 6 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 7. Warunek kopca przestaje obowiązywać. Zamieniamy miejscami węzły 6 i 7.
Po wymianie węzłów 6 i 7 warunek kopca obowiązuje.

7 5 9 6 7 8 10
Dołączamy kolejny węzeł. Powoduje on naruszenie warunku kopca, zatem wymieniamy ze sobą węzły 7 i 8.
Po wymianie węzłów 7 i 8 warunek kopca znów obowiązuje.

7 5 9 6 7 8 10
Dołączenie ostatniego elementu znów narusza warunek kopca. Zamieniamy miejscami węzeł 8 z węzłem 10.
Po wymianie węzłów 8 i 10 warunek kopca został przywrócony na tym poziomie. Jednakże węzeł 10 stał się dzieckiem węzła 9. Na wyższym poziomie drzewa warunek kopca jest naruszony. Aby go przywrócić znów wymieniamy miejscami węzły, tym razem węzeł 9 z węzłem 10.
Po wymianie tych węzłów warunek kopca obowiązuje w całym drzewie - zadanie jest wykonane.

 

Charakterystyczną cechą kopca jest to, iż korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego.

 

Algorytm

Poniżej przedstawiamy algorytm konstrukcji kopca z elementów zbioru.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający elementy do wstawienia do kopca. Numeracja elementów rozpoczyna się od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający kopiec

Zmienne pomocnicze

i - zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu,  i N, i {2,3,...,n}
j,k - indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia,  j,k C
x - zmienna pomocnicza przechowująca tymczasowo element wstawiany do kopca

 

Lista kroków

K01: Dla i = 1, ..., n-1: wykonuj K02...K05
K02:     ji;   k ← (j-1) div 2
K03:     x ← d[i]
K04:     Dopóki d[k] < x: wykonuj
        d[j] ← d[k]
        Jeśli k = 0, to idź do K05
        inaczej  jk; k(j-1) div 2
K05:     d[j] ← x
K06: Zakończ

Uwaga: przy porządku malejącym należy zmienić drugi warunek w kroku K04 z d[k] < x na d[k] > x.

 

Rozbiór kopca

Algorytm

W tym rozdziale nauczymy się rozbierać kopiec.  Zasada jest następująca:

  1. Zamień miejscami korzeń z ostatnim liściem, który wyłącz ze struktury kopca. Elementem pobieranym z kopca jest zawsze jego korzeń, czyli element największy.
  2. Jeśli jest to konieczne, przywróć warunek kopca idąc od korzenia w dół.
  3. Kontynuuj od kroku 1, aż kopiec będzie pusty.

Przykład:

Dokonaj rozbioru następującego kopca:


Operacja Opis

9
Rozbiór kopca rozpoczynamy od korzenia, który usuwamy ze struktury kopca. W miejsce korzenia wstawiamy ostatni liść.
   
Poprzednia operacja zaburzyła strukturę kopca. Idziemy zatem od korzenia w dół struktury przywracając warunek kopca - przodek większy lub równy od swoich potomków. Praktycznie polega to na zamianie przodka z największym potomkiem. Operację kontynuujemy dotąd, aż natrafimy na węzły spełniające warunek kopca.
 
8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
   W nowym kopcu przywracamy warunek kopca.
 
7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
    

W nowym kopcu przywracamy warunek kopca. W tym przypadku już po pierwszej wymianie węzłów warunek koca jest zachowany w całej strukturze.

   
5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
 

Przywracamy warunek kopca w strukturze.

 
4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
      

Przywracamy warunek kopca w strukturze.

    
2 4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem.
            
1 2 4 5 7 8 9
Po wykonaniu poprzedniej operacji usunięcia w kopcu pozostał tylko jeden element - usuwamy go. Zwróć uwagę, iż usunięte z kopca elementy tworzą ciąg uporządkowany.

 

Operację rozbioru kopca można przeprowadzić w miejscu. Jeśli mamy zbiór d[ ] ze strukturą kopca, to idąc od końca zbioru (ostatnie liście drzewa) w kierunku początku zamieniamy elementy z pierwszym elementem zbioru (korzeń drzewa), a następnie poruszając się od korzenia w dół przywracamy warunek kopca w kolejno napotykanych węzłach.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający poprawną strukturę kopca. Elementy są numerowane począwszy od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający elementy pobrane z kopca ułożone w porządku rosnącym

Zmienne pomocnicze

i - zmienna licznikowa pętli pobierającej kolejne elementy z kopca,  i N, i {n-1,...,1}
j,k - indeksy elementów leżących na ścieżce w dół od korzenia,  j,k N
m - indeks większego z dwóch elementów potomnych, m N

 

Lista kroków

K01: Dla i = n - 1, n - 2, ..., 1: wykonuj K02...K08
K02:     d[0] ↔ d[i]
K03:     j ← 0;  k ← 1
K04:     Dopóki (k < i) wykonuj K05...K08
K05:         Jeżeli (k + 1 < i) ∧ (d[k + 1] > d[k]), to mk + 1
        inaczej  mk
K06:         Jeżeli d[m] ≤ d[j], to wyjdź z pętli K04 i kontynuuj następny obieg K01
K07:         d[j] ↔ d[m]
K08:         jmk2j + 1
K09: Zakończ

 

Sortowanie przez kopcowanie

Algorytm

Jeśli przeczytałeś uważnie poprzednie dwa rozdziały, to zasadę sortowania przez kopcowanie zrozumiesz od razu - w zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający elementy do posortowania, które są numerowane począwszy od 0.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający elementy posortowane rosnąco

Zmienne pomocnicze i funkcje

Twórz_kopiec - procedura budująca kopiec z elementów zbioru d[ ]. Kopiec powstaje w zbiorze d[ ].
Rozbierz_kopiec - procedura dokonująca rozbioru kopca utworzonego w zbiorze d[ ]. Wynik rozbioru trafia z powrotem do zbioru d[ ].

 

Lista kroków

K01: Twórz_kopiec
K02: Rozbierz_kopiec
K03: Zakończ algorytm

Ponieważ sortowanie przez kopcowanie składa się z dwóch następujących bezpośrednio po sobie operacji o klasie czasowej złożoności obliczeniowej O(n log n), to dla całego algorytmu klasa złożoności również będzie wynosić O(n log n).

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.