Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Sortowanie stogowe
Heap Sort

SPIS TREŚCI
Podrozdziały

Drzewo binarne (Binary Tree)

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:

obrazek

Pierwszy element d[1] nie posiada poprzednika (ang. predecessor - elementu poprzedzającego w ciągu). Ostatni element d[n] 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).

obrazek

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

Na początek:  podrozdziału   strony 

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:

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

obrazek

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

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

węzeł nadrzędny ma indeks równy [k / 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
obrazek
7 5 9 2 4 6 1
Konstrukcję drzewa binarnego rozpoczynamy od korzenia, który jest pierwszym elementem zbioru, czyli liczbą 7.
obrazek
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.
obrazek
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.
obrazek
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.
Na początek:  podrozdziału   strony 

Zrównoważone drzewa binarne (Balanced Binary Trees)

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.

obrazek

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

Drzewo po prawej stronie nie posiada węzła d[5]. Takiego drzewa nie przedstawimy poprawnie za pomocą tablicy elementów od d[1] do d[7], 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 > n. Jeśli tak, węzeł jest liściem. Jeśli nie, węzeł posiada potomka o indeksie 2k, zatem nie może być liściem

Na początek:  podrozdziału   strony 

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

obrazek

Na powyższym rysunku zaznaczona została ścieżka biegnąca poprzez węzły {d[1], d[3], d[6], d[13]}. Ś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ą:

Na początek:  podrozdziału   strony 

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
Na początek:  podrozdziału   strony 

Zadania dla ambitnych

  1. Zaprojektuj algorytm, który wyznacza ścieżkę od korzenia drzewa binarnego do wskazanego węzła. Na podstawie algorytmu napisz odpowiedni program w wybranym języku programowania.
  2. Wykorzystując zaprojektowany w zadaniu 1 algorytm napisz program, który dla zadanego drzewa binarnego wyznacza wszystkie ścieżki od korzenia do poszczególnych liści.
  3. Zaprojektuj algorytm, który sprawdza, czy istnieje ścieżka pomiędzy dwoma węzłami drzewa binarnego. Na podstawie tego algorytmu napisz program w wybranym języku programowania.
Na początek:  podrozdziału   strony 

Zobacz również na: Tworzenie kopca | Rozbiór kopca | Sortowanie przez kopcowanie


Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.