TI/Algorytmy i struktury danych/Drzewa
Spis treści
Drzewa
Przypomnij sobie krótki wstęp do teorii grafów przedstawiony na początku semestru.
Drzewo jest strukturą składającą się z węzłów i krawędzi.
Węzłem wyróżnionym jest korzeń drzewa (na rysunku Figure 1 korzeniem jest węzeł o wartości 2).
W drzewie nie występują cykle, czyli ścieżki zaczynające się i kończące na tym samym wierzchołku bez powtórzeń krawędzi. Drzewa są też spójne, co oznacza, że między dowolną parą wierzchołków istnieje ścieżka. Stopniem wierzchołka nazywamy liczbę krawędzi z niego wychodzących. W drzewach wprowadza się następujące pojęcia:
- liść — węzeł o stopniu równym jeden, co oznacza, że liście są węzłami połączonymi tylko ze swoim rodzicem. Na rysunku Figure 1 liśćmi są węzły o wartościach 9, 3, 4, 5, 11.
- Synowie — węzły połączone z danym i leżące poniżej. Na rysunku Figure 1 synami są wszystkie węzły oprócz węzła o wartości 2, który jest korzeniem drzewa (ang. root).
- Ścieżka — ciąg krawędzi łączących dwa wierzchołki. Od węzła 4 do węzła 5 mamy następującą ścieżkę — krawędź 4-8, krawędź 8-2, krawędź 2-7, krawędź 7-6, krawędź 6-5.
- Poziom wierzchołka — odległość wierzchołka od korzenia. Przykładowo wierzchołek 6 ma poziom 3.
- Wysokość drzewa — maksymalny poziom drzewa. Wysokość drzewa na rysunku Figure 1 to 4.
- Stopień wierzchołka — liczba krawędzi z nim sąsiadujących. Na rysunku Figure 1 węzeł o kluczu 2 ma stopień 3.
- Stopień drzewa — maksymalny stopień wierzchołka. Drzewo przedstawione na rysunku Figure 2 ma stopień 2.
- Węzeł wewnętrzny — węzeł nie będący liściem — na rysunku Figure 1 węzłami wewnętrznymi są węzły o kluczach 6,7,2, i 8.
drzewo można formalnie zdefiniować rekurencyjnie jako drzewo puste lub korzeń z listą drzew
Drzewa binarne
Drzewo binarne jest drzewem, w którym stopień każdego wierzchołka (liczba połączeń danego wierzchołka) nie jest wyższy niż 3. Drzewo takie przedstawione jest na rysunku Figure 3. Drzewo takie można wygodnie reprezentować w tablicy — jeżeli nadamy wierzchołkowi i-ty element tablicy, jego lewy syn będzie miał indeks 2i+1, a prawy 2i+2 w przypadku języków, w których wektory numerowane są od zera.
Reprezentacja drzewa binarnego przedstawionego na rysunku Figure 3, postaci tablicy jest następująca:
| indeks | klucz |
|---|---|
| 0 | 2 |
| 1 | 7 |
| 2 | 5 |
| 3 | 2 |
| 4 | 6 |
| 5 | |
| 6 | 9 |
| 7 | |
| 8 | |
| 9 | 5 |
| 10 | 11 |
| 12 | |
| 13 | |
| 14 | 4 |
| 15 |
Zadanie
<korzen litera="d"> <lewy litera="b"> <lewy litera="a"> </lewy> <prawy litera="c"> </prawy> </lewy> <prawy litera="f"> <lewy litera="e"> </lewy> <prawy litera="g"> </prawy> </prawy> </korzen>
Napisz funkcję zapisująca drzewo binarne do tablicy (albo listy) zw porządku prefiksowym (do tablicy/listy wpisz artybut/y). Przetestuj swój program na powyższym drzewie.
W ramach zabawy spróbuj także zapisać drzewo w porządku infiksowym i postfiksowym.
Drzewo BST (Binary Search Tree)
Tutaj można obejrzeć symulację działania drzewa BST, jak również różnego innego rodzaju drzewiastych struktur danych.
Drzewo BST (wyszukiwania binarnego) ma następującą własność — dla każdego węzła wszystkie wartości znajdujące się w poddrzewie którego korzeniem jest jego prawy syn mają wartości większe niż on, a w poddrzewie którego korzeniem jest lewy syn mniejsze (albo na odwrót, ważna jest konsekwencja implementacji). Struktura ta jest bardzo pomocna przy wyszukiwaniu.
Załóżmy, że chcemy znaleźć liczbę k. Jeśli k ma wartość większą niż klucz korzenia to rekurencyjnie szukamy w lewym poddrzewie, jeśli mniejszą to w prawym, jeśli równą to znaleźliśmy. Algorytm ten przedstawiony jest na rys. Figure 7.
Drzewo BST wypisane infixowo daje ciąg uporządkowany.
class Wezel(object):
def __init__(self, klucz):
self.lewySyn = None
self.prawySyn = None
self.klucz = klucz
class Wezel(object):
...
def sprawdz(self, klucz, rodzic=None):
if klucz > self.klucz:
if self.lewySyn is None:
return None, None
return self.lewySyn.sprawdz(klucz, self)
elif klucz < self.klucz:
if self.prawySyn is None:
return None, None
return self.prawySyn.sprawdz(klucz, self)
else:
return self, rodzic
class Wezel(object):
def wstaw(self, klucz):
if klucz < self.klucz:
if self.lewySyn is None:
self.lewySyn = Wezel(klucz)
else:
self.lewySyn.wstaw(klucz)
else:
if self.prawySyn is None:
self.prawySyn = Wezel(klucz)
else:
self.prawySyn.wstaw(klucz)
def przeszukaj_drzewo_binarne(wezel, klucz):
if wezel is None:
return None # nie znaleziono klucza
if klucz < wezel.klucz:
return przeszukaj_drzewo_binarne(wezel.lewySyn, klucz)
elif klucz > wezel.klucz:
return przeszukaj_drzewo_binarne(wezel.prawySyn, klucz)
else: # gdy szukany klucz jest rowny kluczowi danego wezla
return wezel.klucz
Zadanie 1
Algorytmy i fragmenty struktur danych opisane na przedstawione na rysunkach Figure 4, Figure 6, Figure 5, Figure 7 złoż w klasę Wezel. Sprawdź, czy wszystkie metody są poprawnie zapisane. Dopisz do klasy Wezel metodę wypisującą drzewo.
Zadanie 2
Do klasy Wezel dodaj metodę wypisującą liczbę synów danego węzła.
Zadanie 3
Porównanie dwóch drzew powinno zachodzić rekurencyjnie. Jeżeli natrafi na jeden różny węzeł w dwóch drzewach powinno zwracać False. Różny węzeł może znaczyć także brakujący liść. Jak argument powinien być przekazywany korzeń drugiego drzewa. Do klasy Wezel dodaj taką metodę.
Usuwanie węzła w drzewie BST
Usuwanięcie węzła może wymagać reorganizacji struktury drzewa w celu zachowania własności BST. Należy rozważyć trzy przypadki
- usuwany węzeł nie ma synów (jest liściem): usunięcie przebiega bez reorganizacji drzewa, wskaźnik do węzła w jego ojcu zastępowany jest wskaźnikiem do węzła pustego
- usuwany węzeł ma jednego syna: dany węzeł usuwamy, a jego syna podstawiamy w miejsce usuniętego węzła
- usuwany węzeł ma dwóch synów: po jego usunięciu wstawiamy w jego miejsce węzeł, który jest jego następnikiem lub poprzednikiem (do wyboru albo implementacja z następnikiem albo z poprzednikiem). Następnik i poprzednik to odpowiednio najbardziej lewy węzeł w prawym podrzewie, lub najbardziej prawy węzeł węzeł w prawym poddrzewie.
else:
rodzic = wezel
nastepnik = wezel.prawySyn
while nastepnik.lewySyn:
rodzic = nastepnik
nastepnik = nastepnik.lewySyn
wezel.klucz = nastepnik.klucz
if rodzic.lewySyn == nastepnik:
rodzic.lewySyn = nastepnik.prawySyn
else:
rodzic.prawySyn = nastepnik.prawySyn
Zadanie 4
Dodaj do klasy metodę usuwającą węzeł o zadanym kluczy z drzewa BST.
Równoważenie drzwa (zadanie domowe)
Przeczytaj artykuł opisujący algorytm równoważenia drzewa DSW. Napisz własną implementację tego algorytmu w Pythonie, używając klasy Wezel.
obiegi drzew
możliwe są następujące obiegi drzew i kolejności odwiedzania:
- prefixowyLP - my, lewy syn, prawy syn
- prefixowyPL - my, prawy syn, lewy syn
- infixowyLP - lewy syn, my, prawy syn
- infixowyPL - prawy syn, my, lewy syn
- postfixowyLP - lewy syn, prawy syn, my
- postfixowyPL - prawy syn, lewy syn, my
obiegi te są powiązane ciekawymi twierdzeniami:
- prefixowyLP = postfixowyPL^{-1}
- prefixowyPL = postfixowyLP^{-1}
- infoxowyLP = infixowyPL^{-1}
Materiały zostały przygotowane na postawie m.in. Binary Search Tree library na blogu Laurenta Luce'a
