Informatyka dla klas II

Sortowanie kopcowe

Drzewo

Drzewo (ang. tree) jest strukturą danych zbudowaną z elementów, które nazywamy węzłami (ang. node). Dane przechowuje się w węzłach drzewa. Węzły są ze sobą powiązane w sposób hierarchiczny za pomocą krawędzi (ang. edge), które zwykle przedstawia się za pomocą strzałki określającej hierarchię. Pierwszy węzeł drzewa nazywa się korzeniem (ang. root node). Od niego "wyrastają" pozostałe węzły, które będziemy nazywać synami (ang. child node). Synowie są węzłami podrzędnymi w strukturze hierarchicznej. Synowie tego samego ojca są nazywani braćmi (ang. sibling node). Węzeł nadrzędny w stosunku do syna nazwiemy ojcem (ang. parent node). Ojcowie są węzłami nadrzędnymi w strukturze hierarchicznej. Jeśli węzeł nie posiada synów, to nazywa się liściem (ang. leaf node), w przeciwnym razie nazywa się węzłem wewnętrznym (ang. internal node, inner node, branch node).
Struktura drzewa    
  A...H – węzły drzewa

strzałki – krawędzie. Zwrot określa kierunek hierarchii rodzić → dziecko.

A – korzeń drzewa
B,C,D  – bracia, synowie węzła A, który jest dla nich ojcem
E,F,G  – bracia, synowie węzła B, który jest dla nich ojcem
H – syn węzła D, który jest dla niego ojcem
A,B,D – węzły wewnętrzne
C,E,F,G,H – liście

 

Za wyjątkiem korzenia wszystkie pozostałe węzły w drzewie posiadają swojego ojca. W normalnym drzewie liczba synów dla dowolnego węzła nie jest ograniczona. Istnieje jednakże bardzo ważna klasa drzew, w których dany węzeł może posiadać co najwyżej dwóch synów. Noszą one nazwę drzew binarnych (ang. binary tree).

Ciąg węzłów połączonych krawędziami nazwiemy ścieżką (ang. path). Od korzenia do określonego węzła w drzewie wiedzie zawsze dokładnie jedna ścieżka prosta, tzn. taka, iż zawarte w niej węzły pojawiają się tylko jeden raz. Długością ścieżki (ang. path length) nazwiemy liczbę krawędzi łączących węzły w ścieżce. Dla naszego drzewa mamy następujące ścieżki proste od korzenia do kolejnych węzłów:

 

Struktura drzewa   Ścieżki
  ścieżka od A do A: długość 0: A
ścieżka od A do B: długość 1: A→B
ścieżka od A do C: długość 1: A→C
ścieżka od A do D: długość 1: A→D
ścieżka od A do E: długość 2: A→B→E
ścieżka od A do F: długość 2: A→B→F
ścieżka od A do G: długość 2: A→B→G
ścieżka od A do H: długość 2: A→D→H

 

Długość ścieżki prostej od korzenia do danego węzła nazywa się poziomem węzła (ang. node level). Korzeń drzewa ma zawsze poziom 0. W naszym drzewie węzły B, C i D mają poziom 1, a E, F, G i H mają poziom 2. Wysokość drzewa (ang. tree height) jest równa największemu poziomowi węzłów (lub najdłuższej ścieżce rozpoczynającej się w korzeniu). Dla naszego drzewa wysokość jest równa 2. Wysokość węzła (ang. node height), to długość najdłuższej ścieżki od tego węzła do liścia. Dla korzenia wysokość węzła jest równa wysokości drzewa:

 

Struktura drzewa   Wysokości węzłów
  węzeł A: wysokość = 2
węzeł B: wysokość = 1
węzeł C: wysokość = 0
węzeł D: wysokość = 1
węzeł E: wysokość = 0
węzeł F: wysokość = 0
węzeł G: wysokość = 0
węzeł H: wysokość = 0

 

Poziom drzewa (ang. tree level, the level of a tree) dla danego węzła to długość ścieżki prostej od korzenia do danego węzła.

 

Struktura drzewa   Poziomy
  Poziom 0: A
Poziom 1: B,C,D
Poziom 2: E,F,G,H

 

Drzewo binarne

Drzewo, w którym węzły mogą posiadać co najwyżej dwóch synów, nazywa się drzewem binarnym (ang. binary tree, B-tree). Węzły potomne nazywamy odpowiednio synem lewym (ang. left child node) i synem prawym (ang. right child node). Drzewa binarne mają ogromne znaczenie w informatyce, ponieważ za ich pomocą można odwzorować również drzewa, których węzły posiadają dowolną liczbę synów – sposób takiego odwzorowania podamy w dalszej części rozdziału.

 

Drzewo binarne    
  A – korzeń, ojciec B i C
B,C – synowie A, B – lewy syn A, C – prawy syn A
D,E – liście, synowie B
F,G – liście, synowie C

 

W drzewie binarnym stopień każdego węzła nie przekracza 3. Stopień korzenia nie przekracza 2.

Regularne drzewo binarne (ang. regular binary tree, proper binary tree) zawiera wyłącznie węzły, których stopień wyjściowy jest albo równy 2 (węzeł posiada dwóch synów – jest węzłem wewnętrznym), albo 0 (węzeł nie posiada synów – jest liściem).

 

Regularne drzewo binarne   Stopnie wyjściowe
  A – stopień wyjściowy 2, węzeł wewnętrzny
B – stopień wyjściowy 2, węzeł wewnętrzny
C – stopień wyjściowy 2, węzeł wewnętrzny
D – stopień wyjściowy 0, liść
E – stopień wyjściowy 0, liść
F – stopień wyjściowy 0, liść
G – stopień wyjściowy 0, liść

 

Dla regularnego drzewa binarnego liczba węzłów na poziomie k-tym jest zawsze równa 2k. Liczba wszystkich węzłów, czyli rozmiar drzewa (ang. binary tree size) jest równa 2p - 1, gdzie p oznacza liczbę poziomów.

 

 

Dla n węzłów liczba poziomów jest równa log2(n+1).

Ponumerujmy poziomami kolejne węzły, idąc od strony lewej do prawej:

 

 

Otrzymane numery węzłów są powiązane ze strukturą hierarchii drzewa prostymi zależnościami:

 

     Jeśli węzeł o numerze k posiada synów, to:

lewy syn ma numer 2k+1
prawy syn ma numer 2k+2

  Jeśli węzeł o numerze k posiada ojca, to:

ojciec ma numer [(k-1) / 2]

[...] oznacza część całkowitą.

 

Węzeł o numerze k znajduje się na poziomie o numerze [log2(k+1)].

Węzeł o numerze k jest wewnętrzny, jeśli 2k+2 < n. W przeciwnym razie węzeł jest liściem.

Własności te pozwalają odwzorowywać regularne drzewo binarne w ciąg elementów i na odwrót

 

 

Kompletne drzewo binarne (ang. complete binary tree) posiada zapełnione węzłami wszystkie poziomy z wyjątkiem ostatniego, jednakże na ostatnim poziomie węzły są zapełnione począwszy od lewej strony.

 

Kompletne drzewo binarne   Niekompletne drzewo binarne
        

 

Kompletne drzewo binarne również da się odwzorować w ciąg węzłów. W takim drzewie liczba elementów n może być mniejsza od maksymalnej liczby węzłów, ponieważ ostatni poziom nie musi posiadać kompletu węzłów. Jednakże w przeciwieństwie do drzewa regularnego węzeł wewnętrzny może posiadać tylko jednego, lewego syna (u nas węzłem takim jest węzeł 4). Dlatego w kompletnym drzewie binarnym o rozmiarze n dla węzła o numerze k zachodzi:

 

2k + 2 > n – węzeł jest liściem

2k + 2 = n – węzeł jest ostatnim węzłem wewnętrznym i posiada tylko lewego syna

2k + 2 < n – węzeł jest węzłem wewnętrznym i posiada obu synów.

 

Poddrzewo (ang. subtree) jest drzewem zawartym w drzewie, gdy jako korzeń przyjmiemy jeden z węzłów. Dla danego węzła drzewa binarnego mogą istnieć dwa poddrzewa: lewe poddrzewo (ang. left subtree) – korzeniem jest lewy syn i analogicznie prawe poddrzewo (ang. right subtree) – korzeniem jest prawy syn:

 

 

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 tablicy.

 

Specyfikacja problemu

Dane wejściowe

T - Tablica z elementami do posortowania. Numeracja rozpoczyna się od 0..
n - Ilość elementów w tablicy,  n symbol N

Dane wyjściowe

T - Tablica z kopcem

Zmienne pomocnicze

i - zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu,  i symbol N,
j,k - indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia,  j,k symbol 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:     xT[i]
K04:     Dopóki (j > 0) ∧ (T[k] < x): wykonuj
        T[j] ← T[k]
        jk
        k ← (j - 1) div 2
K05:     T[j] ← x
K06: Zakończ
 

Rozbiór kopca

Algorytm

Zasada rozbioru kopca 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

T - Tablica zawierająca kopiec. Elementy są numerowane począwszy od 0.
n - Ilość elementów w tablicy,  n symbol N

Dane wyjściowe

T - Tablica z posortowanymi rosnąco elementami

Zmienne pomocnicze

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

 

Lista kroków

K01: Dla i = n - 1, ..., 1: wykonuj K02...K08
K02:     T[0] ↔ T[i]
K03:     j ← 0;  k ← 1
K04:     Dopóki (k < i) wykonuj K05...K08
K05:         Jeżeli (k + 1 < i) (T[k + 1] > T[k]), to mk + 1
        inaczej  mk
K06:         Jeżeli T[m] T[j], to wyjdź z pętli K04 i kontynuuj następny obieg K01
K07:         T[j] ↔ T[m]
K08:         jmkj + j + 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 tablicy tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji tablica zostanie posortowana rosnąco.

 

Specyfikacja problemu

Dane wejściowe

T - Tablica elementów do posortowania, które są numerowane od 0.
n - Ilość elementów w tablicy,  n symbol N

Dane wyjściowe

T - Tablica posortowana 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

 

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). Jest to jeden z szybkich algorytmów sortowania.

 



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.