51

10. Lista liniowa dwukierunkowa

Jest to lista złożona z elementów, z których każdy posiada,

oprócz wskaźnika na element następny, również wskaźnik na
element poprzedni.

Zdefiniujmy element listy dwukierunkowej

struct ELEMD

{ int klucz;

ELEMD * left, * right;

};

Rys. 35 Lista liniowa dwukierunkowa

Lista liniowa dwukierunkowa nie ma wyróżnionego

początku ani końca – jest symetryczna. Rolę wskaźnika do
całej listy pełni tutaj wskaźnik name, którego położenie jest w
zasadzie dowolne, może więc być używany, na przykład, do
wyszukiwania elementów.

Z powyższego wynika również, że algorytmy usuwające

elementy powinny sprawdzać, czy usuwany element nie jest
aktualnie wskazywany przez wskaźnik do całej listy. Jeśli tak,
wskaźnik do całej listy należy wcześniej przesunąć na inny
element.

7

2

4

name

p

52

ELEMD *q = new ELEMD;
p →

→

→

→ left →

→

→

→ right = q;

q →

→

→

→ left = p →

→

→

→ left;

p →

→

→

→ left = q;

q →

→

→

→ right = p;

Rys. 36 Przykładowy algorytm wstawiania nowego

elementu, wskazywanego przez q, przed element
wskazywany przez p (założono, że element stojący
na lewo od p istnieje)

p →

→

→

→ left →

→

→

→ right = p →

→

→

→ right;

p →

→

→

→ right →

→

→

→ left = p →

→

→

→ left;

delete p;

Rys. 37 Przykładowy algorytm usuwania elementu

wskazywanego przez p (przy założeniu, że element
usuwany nie jest elementem skrajnie prawym, ani
skrajnie lewym)

Drzewa i lasy

11. Rekurencyjna definicja drzewa

Drzewo, podobnie jak omawiana w rozdziale poprzednim

lista, jest strukturą, którą możemy zdefiniować w sposób
rekurencyjny.

53

Oto ta definicja:

Niech wierzchołek w (element drzewa) będzie pewnego
typu T, wtedy:

1. Jeżeli dowolna, skończona, rozłączna i nie należąca do

drzewa liczba wierzchołków typu T, do niego
dowiązanych jest drzewami, to w jest drzewem.

2. Zbiór pusty wierzchołków jest drzewem.

Jest to typowa definicja rekurencyjna, w której punkt 2
stanowi warunek stopu definicji.

Pojęcie wierzchołek (węzeł) i dowiązanie (łuk) zostały
zapożyczone z teorii grafów. Poniższy rysunek objaśnia
podaną definicję.

a) b)

. . .

Rys. 38 Rekurencyjna definicja drzewa: a) drzewo puste,
b) drzewo niepuste.

root

root

w

w

1

w

2

w

n

w

11

w

12

w

13

54

Definicje podstawowych pojęć

1. Wierzchołki, które są bezpośrednio dowiązane do

danego wierzchołka, nazywamy jego bezpośrednimi
potomkami, albo bezpośrednimi następnikami (synami
węzła).

2. Z kolei – wierzchołek taki nazywać będziemy

bezpośrednim poprzednikiem (ojcem) tych węzłów.

3. Synów tego samego ojca nazywamy braćmi.

4. Wierzchołek, który nie ma bezpośredniego poprzednika

nazywamy korzeniem drzewa. Korzeniem drzewa
nazywa się też wskazanie do tego elementu. Jest to
jednocześnie wskazanie do całego drzewa.

5. Wierzchołki,

które

nie

mają

bezpośrednich

następników,

nazywamy

liśćmi

drzewa.

6. Elementy nie będące liśćmi nazywamy węzłami

wewnętrznymi drzewa.

7. Drzewem uporządkowanym nazywamy drzewo, w

którym dla każdego węzła wewnętrznego na jego
synach określona jest ta sama relacja liniowego
porządku.

8. Jeżeli dany węzeł ma poziom i, to wszystkie jego

bezpośrednie następniki mają poziom i+1. Założymy,
że korzeń drzewa ma poziom 1.

55

9. Maksymalny poziom wierzchołków drzewa nazywamy

wysokością, albo głębokością drzewa.

10. Stopniem drzewa nazywamy maksymalną liczbę

wierzchołków, jakie można dowiązać do każdego z
węzłów.

11. Ścieżką w drzewie jest ciąg jego wierzchołków

a

1

, a

2

, . . . ,a

n

taki, że dla każdego i = 2, 3, . . . , n para

(a

i-1

, a

i

) jest krawędzią, łączącą dany wierzchołek

wewnętrzny

z

jego

bezpośrednim

potomkiem.

Wierzchołki

wewnętrzne

to

zbiór

wszystkich

wierzchołków

drzewa

za

wyjątkiem

liści.

12. Liczba krawędzi, jaką trzeba przejść od korzenia do

poziomu danego wierzchołka w nazywamy długością
drogi wierzchołka

w. Długość drogi korzenia

wynosi 1. Ogólnie - długość drogi wierzchołka na
poziomie i wynosi i.

13. Lasem nazywać będziemy uporządkowany zbiór

drzew. Uporządkowanie drzew w lesie polega na
uporządkowaniu korzeni kolejnych drzew. Spina się je
w las poprzez umieszczenie wskaźników do ich korzeni
w tablicy, lub w liście wskaźników.

Lista liniowa jednokierunkowa jest szczególnym przypadkiem
drzewa. Jest to drzewo stopnia pierwszego.

12. Drzewo binarne

W praktyce używa się zwykle drzew niewysokiego stopnia,

na przykład drugiego (mówimy wtedy o drzewie binarnym).

56

Rys. 39 Przykład drzewa binarnego ( ptr - wskazanie

dowolnego węzła drzewa)

Algorytm tak zwanego naturalnego przekształcenia
dowolnego lasu w drzewo binarne

Jest

to

algorytm,

który umożliwia przekształcenie

dowolnego lasu, złożonego z dowolnej ilości drzew o różnych
stopniach, w pojedyncze drzewo binarne. Jest zupełnie
naturalnym, że algorytmy obsługi drzew o ustalonym,
niewysokim stopniu, będą prostsze i bardziej efektywne niż
algorytmy dotyczące drzew charakteryzujących się dość dużą
dowolnością.

Algorytm

tak

zwanego

naturalnego

przekształcenia

dowolnego lasu w drzewo binarne skonstruować można wg.
poniższych kroków:

1. Przyjmij za korzeń drzewa binarnego korzeń pierwszego

drzewa w lesie.

2. Przenoś kolejne węzły drzew lasu do drzewa binarnego w ten

sposób, aby:
2.1. ich pola left wskazywały listę wiązaną synów tego węzła
w drzewie oryginalnym,
2.2. lista ta była wiązana poprzez pola right każdego z
przenoszonych węzłów,
2.3. zasada ta dotyczy również wiązania korzeni
poszczególnych drzew lasu.

root

7

8

2

5

1

4

ptr

57

las 0 1 2 ... N-1

Rys. 40 Las złożony z dwóch drzew. N-elementowa tablica
wskaźników las przechowuje wskazania do
kolejnych drzew w lesie

Rys. 40 przedstawia przykładowy las złożony z dwóch

drzew o różnym stopniu, rys. 41 – drzewo binarne otrzymane
z przekształcenia tego lasu za pomocą wyżej omawianego
algorytmu.
Po przekształceniu lasu w drzewo binarne i wykonaniu na
nim wszystkich niezbędnych operacji, takich jak: wyszukanie
węzła, modyfikacja jego zawartości, bądź nawet usunięcie lub
wstawienie nowego węzła, drzewo binarne można z powrotem
przekształcić do pierwotnej, naturalnej postaci.

1

3

2

7

8

13

19

17

14

4

18

16

15

6

5

12

9

11

10

58

Rys. 41 Drzewo binarne powstałe z przekształcenia lasu
przedstawionego na rys.40

Przeglądanie drzewa binarnego

Niech Q(ptr) będzie operacją, którą trzeba wykonać na

węźle wskazywanym przez ptr, oraz wszystkich węzłach
leżących poniżej węzła wskazywanego przez ptr (patrz
rys. 39). Jeśli ptr = root, czyli wywołamy procedurę Q dla
wskazania korzenia drzewa, wtedy procedura ta wykonana
zostanie dla całego drzewa.

Rys. 42 Węzły drzewa binarnego

root

7

8

12

14

3

1

2

19

17

6

5

4

12

9

11

10

18

16

15

C

B

A

ptr

59

Rekurencyjną metodę zapewniającą przejrzenie całego

drzewa o dowolnym kształcie i rozmiarach począwszy od
węzła wskazywanego przez ptr (węzeł A na rys. 42)
sformułować można następująco:

Wykonaj żądaną operację na węźle, w którym się znajdujesz

a następnie zgodnie z przyjętą zasadą odwiedź lewy
wierzchołek dowiązany, następnie zgodnie z przyjętą zasadą
odwiedź prawy wierzchołek dowiązany.

W tym opisie metody najważniejszym jest sformułowanie

„zgodnie z przyjętą zasadą”. Tutaj bowiem ukryte jest
rekurencyjne wywołanie metody. Uzyskany efekt najlepiej
obrazuje poniższy rysunek.

Rys. 43 Kolejność wykonywania operacji Q(ptr) na

węzłach drzewa binarnego przy użyciu metody
preorder.

Mamy tu do czynienia ze schematem odwiedzania węzłów

drzewa binarnego, który nazwany został metodą zstępującą,
albo metoda porządku poprzedzającego (z ang. preorder ).

root

1

3

4

5

8

2

ptr

7

6

60

Jest to schemat A – B – C. A oznacza wykonanie operacji

na węźle, B lub C - jedynie jego odwiedzenie.

Dwa dalsze możliwe schematy to:

• B – A – C inorder - metoda wstępująca lub

porządek następujący,

• B – C – A postorder - metoda symetryczna lub

porządek wewnętrzny.

Rekurencyjna funkcja zapewniająca, przy zastosowaniu
metody preorder, wykonanie procedury Q(ptr) dla całego
poddrzewa wskazywanego przez ptr będzie miała w notacji
języka C/C++ postać:

void preorder ( BIN *ptr)

{

if (ptr)

{

Q(ptr);

preorder(ptr → left); preorder(ptr → right);

}

}

13. Drzewa binarnych poszukiwań

Niech poniższy ciąg nie powtarzających się liczb

całkowitych będzie ciągiem kluczy, które chcemy wstawić do
drzewa binarnego w sposób uporządkowany.

7 3 6 9 1 8 5

61

Poszukując liścia, którego następnikiem ma być kolejny

wstawiany wierzchołek, zastosujmy następującą rekurencyjną
metodę:

1. jeżeli wartość wstawiana jest mniejsza od wartości klucza

badanego węzła, należy poprzez pole left przejść do
lewego węzła,

2. jeżeli wartość wstawiana jest większa od wartości klucza

badanego węzła, należy poprzez pole right przejść do
prawego węzła,

3. powyższe można zakończyć po napotkaniu węzła,

którego lewe, lub prawe wskazanie jest wskazaniem
pustym, wskazania tego należy użyć w celu wstawienia
węzła.

Zauważmy, że poszukując miejsca wstawienia nowego

węzła poruszamy się wzdłuż jednej tylko ścieżki w drzewie i
że miejsce wstawienia jest tylko jedno.

Wyżej opisana metoda wstawiania węzłów do drzewa

binarnego, chociaż ma w istocie charakter rekurencyjny (pk. 3
metody stanowi warunek stopu), to ze względu na to, że
poruszamy się wzdłuż jednej tylko ścieżki, może być łatwo
zrealizowana za pomocą algorytmu iteracyjnego.

Otrzymane w ten sposób drzewa binarne, ze względu na swe

szczególne, opisane niżej, własności nazywamy drzewami
binarnych poszukiwań (DBP).

62

Rys. 44 Drzewo binarnych poszukiwań wygenerowane po

otrzymaniu ciągu kluczy 7 3 6 9 1 8 5

Generowanie drzew binarnych poszukiwań stanowi jedną z

najdoskonalszych metod sortowania informacji. Aby bowiem
znaleźć w drzewie wierzchołek o określonej wartości klucza,
lub stwierdzić, że klucz o takiej wartości nie występuje w
drzewie, wystarczy poruszać się wzdłuż jednej tylko ścieżki.

Oto pełna definicja drzewa binarnych poszukiwań:

Drzewem binarnych poszukiwań nazywać
będziemy drzewo binarne, w którym dla
każdego węzła wewnętrznego, klucz jego
lewego następnika jest mniejszy, a klucz
prawego następnika – większy, od klucza
tego węzła.

Maksymalna liczba porównań, jakie trzeba wykonać, aby

znaleźć jakikolwiek wierzchołek, jest równa wysokości DBP.
Oczywiście im drzewo jest mniej zrównoważone (ma większą
wysokość), tym maksymalna liczba porównań jest większa.

root

7

1

8

5

9

3

ptr

6

63

W idealnym przypadku - drzewa dokładnie wyważonego,

drzewo binarne o wysokości n zawiera aż 2

n

– 1 węzłów.

Korzyści, jakie osiągamy z użycia DBP do sortowania danych,
wzrastają więc nieprawdopodobnie szybko ze wzrostem ilości
tych danych, co jest kolejną pozytywną cechą DBP. Obrazuje
to poniższa tabela

Ilość węzłów w DBP

Maksymalna liczba

porównań

1
3

15

1023

16383
65535

1
2
4

10
14
16

Rys. 45 Zależność między ilością węzłów w DBP a

maksymalną ilością porównań, jakich trzeba
dokonać, aby znaleźć wierzchołek o żądanym
kluczu w dokładnie wyważonym DBP.

Algorytm usuwania węzłów różnych od korzenia w DBP
rozbić można na trzy przypadki:

• jeśli węzeł usuwany jest liściem, wystarczy zwolnić

pamięć dla tego węzła a jego wskazaniu przypisać
wskazanie puste,

• jeśli węzeł usuwany ma jednego potomka, należy

wskazaniu usuwanego węzła przypisać wskazanie tego
potomka,

• natomiast jeśli węzeł usuwany ma dwóch potomków,

należy wskazaniu tego węzła przypisać wskazanie
lewego potomka, a następnie – wypięte w ten sposób
poddrzewo, rozpoczynające się od prawego następnika

64

usuwanego węzła, wpiąć do DBP tak jakby się wpinało
nowy pojedynczy węzeł.

14. Drzewa zrównoważone i idealnie zrównoważone

Jak już zauważyliśmy, korzyści jakie wynosimy, używając

drzew binarnych poszukiwań, są tym mniejsze, im bardziej
uporządkowany jest ciąg kluczy kolejno wstawianych węzłów.
W skrajnym przypadku, to jest uporządkowanego ciągu
kluczy, drzewo binarnych poszukiwań degeneruje się do
uporządkowanej

listy

liniowej,

gdzie

średni

czas

wyszukiwania jest tylko rzędu n/2 (n jest ilością węzłów).

W takich sytuacjach warto konstruować tak zwane drzewa

zrównoważone i drzewa idealnie zrównoważone.

Drzewem zrównoważonym nazywamy drzewo binarne, w

którym dla każdego węzła wysokość jego lewego i prawego
poddrzewa różni się nie więcej niż o jeden. Od nazwisk
odkrywców zostały one również nazwane drzewami AVL.

a) b)

Rys. 46 Przykłady drzew: a) drzewo zrównoważone,

b) drzewo idealnie zrównoważone

3

4

5

root

6

3

root

5

4

6

7

65

Z kolei drzewem idealnie zrównoważonym nazywać

będziemy drzewo binarne, w którym wszystkie liście znajdują
się na jednym, lub dwóch poziomach. Oczywiście nie każde
drzewo

zrównoważone

musi

być

drzewem

idealnie

zrównoważonym.

15. Drzewa z priorytetem (HPO-drzewa albo Kopce).
Sterty

W rozdziale poświęconym listom omówiliśmy listy z

priorytetem (HPO-kolejki). Zupełnie podobne zastosowania
mają drzewa z priorytetem, zwane również HPO-drzewami,
lub kopcami.

HPO-drzewa są to drzewa binarne uporządkowane według

priorytetów i zbudowane według zasady:

Dla każdego węzła wewnętrznego
priorytety jego następników są nie
większe od priorytetu tego węzła.

Rys. 47 Przykładowy kopiec. „Dymki” z wartością 11 w
środku wskazują dopuszczalne miejsca wstawienia
węzła o wartości priorytetu równej 11.

20

root

17

15

17

14

10

10

13

3

7

11

11

11

11

11

ptr

66

W HPO-drzewie węzeł o najwyższym priorytecie znajduje

się zawsze w korzeniu. Podobnie jak w HPO-kolejce do węzła
tego istnieje bezpośredni (a więc bardzo szybki) dostęp
poprzez wskazanie do całego drzewa.

Jak już o tym wcześniej mówiono, im z wyższym drzewem

mamy do czynienia, tym dłuższy jest czas wyszukiwania
węzłów. Czas ten jest najkrótszy z możliwych dla drzewa
idealnie zrównoważonego, gdzie złożoność obliczeniowa
algorytmu wyszukiwania wynosi O(log N). Otrzymanie
drzewa idealnie zrównoważonego dla kopca nie jest
oczywiście zawsze możliwe. (Ćwiczenie: dlaczego ?). Można
jedynie zadbać o to, aby algorytmy wstawiające, lub
usuwające

węzły

„dbały”

o

możliwie

największe

zrównoważenie HPO-drzewa.

Natomiast, jeśli zrezygnować z uporządkowania węzłów w

wyżej omawianym drzewie i zażądać, aby drzewo było
idealnie zrównoważone, otrzymamy drzewo binarne o nazwie
sterta.

16. Drzewa decyzyjne

Drzewa decyzyjne najczęściej służą do wyodrębniania

wiedzy z zestawu przykładów (

eksploracja danych

).

Załóżmy, że posiadamy zestaw przykładów, opisanych przy

pomocy kilku atrybutów. Z każdym obiektem zwiążmy jakąś
decyzję (to co otrzymaliśmy nazywamy

tabelą decyzyjną

).

Wiek Płeć Wykształcenie Języki obce Doświadczenie Ogólna prezentacja Przyjęty

25

m

2

4

1

4

nie

22

k

4

3

4

2

nie

21

m

4

5

5

4

tak

29

m

1

3

2

3

nie

Rys. 48. Przykładowa tabela decyzyjna

67

Załóżmy,

że

tabelę

decyzyjną

stworzono

w

celu

zautomatyzowania procesu przyjmowania kandydatów do
pracy w dużej firmie. Rzeczywiste tabele tego typu liczą
nawet setki wierszy.

W naszym przykładzie wprowadzono atrybuty decyzyjne:

Płeć, Wykształcenie, Języki obce, Doświadczenie i Ogólna
prezentacja, oraz - atrybut decyzyjny: Przyjęty. Wartości
atrybutów decyzyjnych (za wyjątkiem płci) są kodowane w
skali od 1 do 5. Atrybut decyzyjny przyjmuje dwie wartości:
tak, nie.

Na podstawie tabeli decyzyjnej tworzymy drzewo, którego
węzłami są poszczególne atrybuty, gałęziami wartości
odpowiadające tym atrybutom, a liście tworzą poszczególne
decyzje. Na podstawie przykładowych danych wygenerowano
następujące drzewo:

Rys. 49. Przykładowe drzewo decyzyjne stopnia trzeciego

68

Drzewo w takiej postaci odzwierciedla, w jaki sposób na
podstawie

atrybutów

były

podejmowane

decyzje

klasyfikujące. Zaletą tej reprezentacji jest jej czytelność dla
człowieka. Łatwo tez zapisać algorytm klasyfikujący.

17. Wyrażenia kropkowe

Bardzo szczególną postacią drzew są drzewa przechowujące
tzw. wyrażenia kropkowe.

Reprezentantem wyrażenia kropkowego jest drzewo
binarne uzupełnione (w którym wszystkie węzły
wewnętrzne mają dwóch następników), posiadające
etykiety (wartości) tylko na liściach.

( ( a . ( b . c ) ) . d )

a) b)

Rys. 50 Przykład wyrażenia kropkowego: a) reprezentacja
w postaci drzewa, b) zapis „kropkowy”

root

a

c

b

d

69

Wyrażenia kropkowe mają dwa rodzaje węzłów: węzły

wewnętrzne bez etykiet (ich celem jest przechowanie
informacji o strukturze całego wyrażenia kropkowego), oraz
„normalne” węzły na liściach drzewa.

Możemy więc przy ich pomocy, na przykład:

• przedstawić strukturę rozgrywek piłkarskich:
( ( Wisła . ( Legia . Widzew ) ) . Amica )
• albo też przypisując węzłom kropkowym operatory

arytmetyczne, przedstawić strukturę wyrażenia
arytmetycznego: (( a * ( b + c )) – d ).

W pierwszym przykładzie, kropka pełnić może role

operatora wyłaniającego zwycięzcę lewego i prawego
argumentu, w drugim – operatora pozwalającego znaleźć
wartość wyrażenia arytmetycznego lewego i prawego
argumentu. Jest to więc bardzo wygodna, w pełni dynamiczna,
forma przechowywania informacji o strukturze.

K o n i e c c z ę ś c i 4