TI/Algorytmy i struktury danych/Drzewa

Z Brain-wiki


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.

Przykład drzewa.

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

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

Przykład drzewa binarnego

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
Figure 4: Inicjalizowanie klasy węzeł.
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
Figure 5: Sprawdzenie czy wartość jest w drzewie BST.
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)
Figure 6: Wstawianie do drzewa BST.
 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
Figure 7: Przeszukiwanie drzewa binarnego.
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