Algorytmy i struktury danych

Definicja drzewa



Drzewo to struktura umożliwiająca
przechowywanie danych zbudowana z
węzłów oraz wskaźników do potomków.



Drzewa rysuje się w sposób odwrotny,
niż rosną one w przyrodzie. Na szczycie
struktury znajduje się korzeń – węzeł nie
mający ojca, a na samym dole
umiejscowione są liście - nie
posiadające synów.

Drzewa binarne



Odmianą drzew są drzewa binarne. Są to

struktury, w których każdy węzeł posiada co

najwyżej dwóch synów – lewego i prawego.



Rozmieszczenie elementów w drzewie nie

jest przypadkowe. Wszystkie elementy

znajdujące się w lewym poddrzewie są

mniejsze od swojego ojca, natomiast

elementy prawego poddrzewa są większe

od ojca. Reguła ta obowiązuje wszystkie

poddrzewa.



Np. wszystkie elementy lewego

poddrzewa piętnastki są mniejsze od

niej, a wszystkie elementy prawego są

od niej większe (inaczej niż w kopcu!).

Dodawanie elementu



Aby wstawić nowy element do drzewa należy

począwszy od korzenia porównywać dany

element z węzłem i jeżeli jest on mniejszy od

wartości przechowywanej w tym węźle to

poruszać się w lewo po drzewie, w

przeciwnym wypadku poruszać się w prawo.



Wędrujemy tak długo, aż dojdziemy do

miejsca, w którym napotkany wskaźnik do

potomka w węźle będzie wskazywał na NULL

(co oznacza, że niżej nic nie ma).



Wtedy wstawiamy nowy węzeł w to miejsce,

a wspomniany wskaźnik ustawiamy tak, aby

wskazywał na nowy węzeł.

Wyszukiwanie elementu



Przeszukiwanie drzewa binarnego jest

bardzo podobne do wstawiania.



Rozpoczynając od korzenia porównujemy

wartość napotkanego węzła z szukaną

liczbą. Gdy to nie jest szukany element

to, jeśli szukana liczba jest mniejsza od

tej przechowywanej w węźle to idziemy

w lewo, w przeciwnym wypadku

poruszamy się w prawo.



Pomijanie podczas przeszukiwania

niektórych poddrzew możliwe jest dzięki

wspomnianemu specjalnemu

rozmieszczeniu elementów w drzewie.



Jeżeli przejdziemy całe drzewo
(natkniemy się na NULL) i żadna
napotkana wartość nie
odpowiadała naszej liczbie, to
oznacza to, że liczby nie ma w
szukanym węźle.

Przykłady wyszukiwań

Niebieska strzałka to poszukiwanie 13
(znaleziono), czerwona to poszukiwanie 22 (nie
ma w drzewie).

Element minimalny i
maksymalny



Jeżeli chcemy znaleźć element minimalny
(maksymalny) w drzewie to poruszamy
się maksymalnie w lewo (prawo).



Specyficzne rozmieszczenie elementów w
drzewie sprawia, że element minimalny
znajduje się zawsze w najbardziej
„wysuniętym na lewo” węźle, a element
maksymalny w najbardziej „wysuniętym
na prawo” węźle drzewa.

Usuwanie elementu

Przy usuwaniu elementu możliwe są 3

przypadki:

usuwany węzeł nie ma potomstwa.

usuwany węzeł posiada jednego
potomka.

usuwany węzeł posiada aż dwóch
potomków.

Usuwanie: przypadek 1 -
usuwany węzeł nie ma
potomstwa

Usuwamy element (zwalniamy pamięć)

Rodzic usuniętego ma teraz wskazywać na
NULL.

Usuwanie: przypadek 2 -
usuwany węzeł ma jednego
potomka



Zwalniamy pamięć



Rodzic usuwanego elementu ma wskazywać zamiast

na usuwany element na jego (jedynego) potomka.

Usuwanie: przypadek 3 -
usuwany węzeł ma dwóch
potomków



zamieniamy wartość do usunięcia z wartością
minimalną w prawym poddrzewie usuwanego węzła
(na rysunku otoczone przerywaną linią) lub z
wartością maksymalną w lewym poddrzewie.



Następnie usuwamy żądany element (aktualnie
będzie on minimalnym w prawym poddrzewie lub
maksymalnym w lewym poddrzewie).

Przechodzenie drzewa w
głąb i wszerz



Aby wypisać elementy znajdujące
się w drzewie można skorzystać z
jednej z dwóch metod
przechodzenia drzewa:

1. w głąb
2. wszerz

Przechodzenie w głąb



Pierwsza z nich to metoda zrealizowana

rekurencyjnie. Najpierw zostanie wypisane

lewe poddrzewo, a następnie prawe.



Istnieje sześć metod realizacji tego

wypisywania. Różnią się one kolejnością

wykonywanych operacji. Jeżeli wypisywanie to

jest realizowane rekurencyjnie to należy

wykonać trzy operacje: wypisać węzeł,

wywołać funkcję dla lewego potomka,

wywołać funkcję dla prawego potomka.



Kolejność wykonania tych operacji będzie

decydowała o sposobie wypisania danych.

Sześć metod wypisywania w
głąb

Sześć metod wypisywania

(W- wypisz węzeł,

P- wywołaj funkcję dla prawego syna,

L – wywołaj funkcję dla lewego syna):



WLP



WPL



LWP



PWL



LPW



PLW



LWP - wypisze wartości z drzewa
rosnąco,



PWL - wypisze wartości z drzewa
malejąco.



Jest to zgodne z zasadami, z jakimi
wywoływana jest rekurencja.

Przechodzenie wszerz



Elementy będą wypisywane
poziomami.



Najpierw zostaną wypisane elementy
z najwyższego poziomu (korzeń),
potem kolejnego, a na końcu z
najniższego poziomu (liście w
niezrównoważonym drzewie mogą się
znajdować na różnych poziomach).



Do przechodzenia wszerz wykorzystujemy

kolejkę. Na początku wrzucamy do kolejki

korzeń. Następnie wyciągamy korzeń

(wypisujemy go) z kolejki, a wstawiamy do

niej potomstwo korzenia.



Czynność wyciągania węzła z kolejki i

wrzucania jego potomstwa powtarzamy

dopóty, dopóki w kolejce coś się znajduje.



Jeśli wyciągany element nie posiada

potomstwa to do kolejki nic nie zostanie

dodane.

Drzewo zrównoważone



Drzewo zrównoważone to takie,
które ma maksymalnie wypełnione
wszystkie poziomy z wyjątkiem
ewentualnie ostatniego. Tam
elementy są rozlokowane od lewej
strony, ale niekoniecznie
wypełniają cały poziom.

Korzyść ze zrównoważenia
drzewa



Drzewo zrównoważone umożliwia znacznie szybsze

jego przeszukiwanie.



W najgorszym przypadku nasze drzewo mogło by

mieć kształt listy. Wtedy, aby przeszukać taką

strukturę należy sprawdzić wszystkie n węzłów

drzewa.



W najlepszej sytuacji, gdy drzewo będzie idealnie

zrównoważone wystarczy sprawdzić log





węzłów.



Nietrudno zauważyć, że różnica w ilości porównań

jest znaczna, np. dla 10 000 elementów w

najgorszym przypadku należałoby sprawdzić

właśnie 10 000 węzłów, a w najlepszym jedynie 14.

Równoważenie drzewa –
Metoda z wykorzystaniem
pomocniczej tablicy



Najpierw wykorzystując metodę przechodzenia

drzewa w głąb zrzucamy wszystkie elementy

drzewa do tablicy. Musi to być metoda LWP

(elementy muszą być posortowane rosnąco).



Następnie, wykorzystując rekurencję,

dodajemy elementy do drzewa. Robimy to w

taki sposób, że dodajemy element środkowy

tablicy, a następnie wywołujemy funkcje dodaj

dla lewej części tablicy i prawej części.



Nasza funkcja będzie miała dwa argumenty –

lewy i prawy indeks tablicy. Pierwsze

wywołanie funkcji nastąpi dla całej tablicy.

Równoważenie drzewa:
Algorytm DSW



Metoda ta nie wymaga użycia
dodatkowej tablicy.



Polega ona na obracaniu drzewa w
prawo (lewo) aż do uzyskania listy, a
następnie obracaniu go w lewo (prawo),
aż do uzyskania drzewa
zrównoważonego.



Podczas tych operacji obowiązują
pewne zasady.

Przykład równoważenia
przez DSW, Etap 1 –
obracanie w prawo



Lewy syn korzenia staje się korzeniem, a

prawe potomstwo tego syna staje się

lewym potomstwem dawnego korzenia,

który wędruje w dół.



Dokonujemy tego tak długo, aż
korzeń nie będzie miał lewego
syna, a następnie to samo robimy
dla wszystkich prawych potomków.

Korzeń nie ma już lewego syna, wykonujemy
obrót dla pierwszego prawego potomka, który
posiada lewego syna (jest to 10). Prawe
poddrzewo węzła, który idzie w gorę (siódemki)
jest przyczepiane jako lewe poddrzewo węzła,
który idzie w dół (dziesiątki).