Tekst źródłowy strony TI/Algorytmy i struktury danych/Drzewa



== Drzewa ==

Przypomnij sobie [[TI/Wstęp_do_programowania_obiektowego#Kr.C3.B3tki_wst.C4.99p_do_teorii_graf.C3.B3w|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.
[[Plik:przykladowe_drzewo.svg|thumb|<figure id="fig:1"/>Przykład drzewa.]]
Węzłem wyróżnionym jest korzeń drzewa (na rysunku <xr id="fig: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ść &mdash; węzeł o stopniu równym jeden, co oznacza, że liście są węzłami połączonymi tylko ze swoim rodzicem. Na rysunku <xr id="fig:1"/> liśćmi są węzły o wartościach 9, 3, 4, 5, 11.
* Synowie &mdash; węzły połączone z danym i leżące poniżej. Na rysunku <xr id="fig: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 &mdash; 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ę &mdash; krawędź 4-8, krawędź 8-2, krawędź 2-7, krawędź 7-6, krawędź 6-5.
* Poziom wierzchołka &mdash; odległość wierzchołka od korzenia. Przykładowo wierzchołek 6 ma poziom 3.
* Wysokość drzewa &mdash; maksymalny poziom drzewa. Wysokość drzewa na rysunku <xr id="fig:1"/> to 4.
* Stopień wierzchołka &mdash; liczba krawędzi z nim sąsiadujących. Na rysunku <xr id="fig:1"/> węzeł o kluczu 2 ma stopień 3.
* Stopień drzewa &mdash; maksymalny stopień wierzchołka. Drzewo przedstawione na rysunku <xr id="fig:2"/> ma stopień 2.
* Węzeł wewnętrzny &mdash; węzeł nie będący liściem &mdash; na rysunku <xr id="fig: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
[[Plik:przykladowe_drzewo_wycinek.svg|thumb|<figure id="fig:2"/>Przykład drzewa.]]
===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 <xr id="fig:3"/>. Drzewo takie można wygodnie reprezentować w tablicy &mdash; 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. 
[[Plik:Binary_tree.svg|thumb|<figure id="fig:3"/> Przykład drzewa binarnego]]

Reprezentacja drzewa binarnego przedstawionego na rysunku <xr id="fig:3"/>, postaci tablicy jest następująca: 
{|class="wikitable"
!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)====
[http://people.ksp.sk/~kuko/bak/ 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ść &mdash; 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. <xr id="fig:szukanie_BST"/>.

Drzewo BST wypisane infixowo daje ciąg uporządkowany.
<figure id="fig:init">
<source lang="python">
class Wezel(object):
    def __init__(self, klucz):
        self.lewySyn = None
        self.prawySyn = None
        self.klucz = klucz
</source>
<caption>Inicjalizowanie klasy węzeł.</caption>
</figure>
<figure id="fig:sprawdz">
<source lang="python">
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
</source>
<caption>Sprawdzenie czy wartość jest w drzewie BST.</caption>
</figure>
<figure id="fig:wstaw">
<source lang="python">
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)
</source>
<caption>Wstawianie do drzewa BST.</caption>
</figure>
<figure id="fig:szukanie_BST">
<source lang="python">
 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  
</source>
<caption>Przeszukiwanie drzewa binarnego.</caption>
</figure>
=====Zadanie 1=====
Algorytmy i fragmenty struktur danych opisane na przedstawione na rysunkach <xr id="fig:init"/>, <xr id="fig:wstaw"/>, <xr id="fig:sprawdz"/>, <xr id="fig:szukanie_BST"/> złoż w klasę <tt>Wezel</tt>. Sprawdź, czy wszystkie metody są poprawnie zapisane. Dopisz do klasy <tt>Wezel</tt> metodę wypisującą drzewo.
=====Zadanie 2=====
Do klasy <tt>Wezel</tt> 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ć <tt>False</tt>. Różny węzeł może znaczyć także brakujący liść. Jak argument powinien być przekazywany korzeń drugiego drzewa. Do klasy  <tt>Wezel</tt> 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.

<source lang="python">
    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

</source>

===== Zadanie 4 =====
Dodaj do klasy metodę usuwającą węzeł o zadanym kluczy z drzewa BST.
===== Równoważenie drzwa (zadanie domowe)=====
Przeczytaj [http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf artykuł] opisujący algorytm równoważenia drzewa DSW. Napisz własną implementację tego algorytmu w Pythonie, używając klasy <tt>Wezel</tt>.

==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}


<small>Materiały zostały przygotowane na postawie m.in. [http://www.laurentluce.com/?p=166 Binary Search Tree library na blogu Laurenta Luce'a]</small>