Wpis opublikowany przez Hakken
829 wyświetleń
Abstrakt
Aby wprowadzić pewną hierarchię i porządek przy rozważaniu grafów wprowadzono termin drzewa. Różne rodzaje drzew są różnymi wariacjami na temat grafów, umożliwiając łatwe (szybkie) uzyskiwanie informacji właśnie ze względu na większe uporządkowanie.
Uwaga, przed lekturą zachęcam do zapoznania się z tekstem dotyczącym grafów (link) jak i innych tekstów na tym blogu.
Drzewa wolne
Drzewem wolnym nazwiemy spójny, acykliczny graf. Zbiór rozłącznych drzew nazwiemy lasem.
Przykład:
Drzewo
Las
Drzewa ukorzenione
Drzewo ukorzenione to takie drzewo wolne, w którym wyróżniamy jeden element (korzeń).
Wierzchołki takiego drzewa często nazywa się węzłami.
Drzewa rysuje się zwyczajowo korzeniem u góry, przykładowo:
Tutaj korzeń oznaczyłem podwójnym okręgiem, ale raczej nie będę tego robił, i będę zakładał, że węzeł na górze rysunku do którego nic nie wchodzi jest korzeniem.
Oznaczenia
Rozważmy węzeł x drzewa ukorzenionego T (którego korzeniem niech będzie r). Każdy węzeł na ścieżce z r do x nazwiemy przodkiem x. X jest natomiast potomkiem każdego z tych węzłów.
Na obrazku sprawa wygląda dość jasno - jeżeli na jakiejś ścieżce węzeł a jest wyżej niż węzeł b, to a jest potomkiem b, natomiast b jest przodkiem a.
Poddrzewo o korzeniu x to drzewo złożone z potomków x (i x jest wtedy korzeniem takiego drzewa). Na rysunku jest to tak, jakby "odciąć" jakiś węzeł od reszty drzewa.
Poprzednik x to taki węzeł y, że z y do x jest bezpośrednie połączenie. Wtedy też x jest nazywany następnikiem lub synem lub (w ramach równości płci...) dzieckiem y.
Jeżeli jakiś węzeł nie ma synów (będę raczej stosował to określenie, chociaż w dzisiejszym świecie jest to dość niebezpieczne, ale cóż... żyję na krawędzi 
) to nazywany jest liściem.
Stopień węzła to liczba jego synów.
Głębokość węzła to długość ścieżki od korzenia do tego węzła.
Drzewo uporządkowane to takie, w którym wszyscy synowie są uporządkowani (czyli w jakiś sposób odróżnialni, mogą być pokolorowani czy też ponumerowani).
Drzewa binarne
Drzewo binarne to takie drzewo, że każdy wierzchołek ma co najwyżej dwóch synów (lewego i prawego). Warto przy tym zauważyć, że dwa drzewa: jedne z korzeniem i prawym synem a drugie z korzeniem i lewym synem są różne nawet jeśli wartości w węzłach są takie same.
Przykład:
Drzewa wyszukiwań binarnych - BST
Drzewo BST to takie drzewo binarne, że jeżeli wartość węzła x wynosi y, to w jego lewym poddrzewie wszystkie węzły będą miały wartość mniejszą niż y, a w prawym większą niż y.
Co nam to daje? W normalnym drzewie podczas szukania konkretnej wartości musimy sprawdzić każdy węzeł. W drzewie BST wystarczy tyle operacji, ile wynosi głębokość tego drzewa (porównujemy z wartością w korzeniu, schodzimy w jedną stronę, znowu porównujemy, schodzimy, itd.).
Obiegi drzew
Możemy obchodzić drzewa na trzy sposoby (no, możemy oczywiście na znacznie więcej, ale te trzy są standardowe): prefixowo, infixowo, postfixowo.
Obiegi rozpatrujemy w ramach jakiejś operacji, weźmy na przykład wypisanie wartości danego węzła.
Przy obiegu prefixowym najpierw wypiszemy siebie, później (prefixowo) lewe poddrzewo, a następnie (również prefixowo) prawe poddrzewo.
Przy obiegu infixowym najpierw infixowo wypiszemy lewe poddrzewo, następnie siebie i na końcu (infixowo) prawe poddrzewo.
Jak łatwo zgadnąć przy obiegu postfixowym najpierw postfixowo wypiszemy lewe poddrzewo, później prawo poddrzewo i na końcu siebie.
Ciekawa obserwacja jest taka, że przy wypisaniu infixowo drzewa BST (z angielskiego BST to binary search tree, więc zasadniczo zwrot "drzewo BST" jest pleonazmem, bo BST samo w sobie zawiera słowo "drzewo", ale zwyczajowo tak się mówi) otrzymamy ciąg posortowany (ściśle monotoniczny).
Proponuję jako ćwiczenie przeprowadzić na kartce (albo w myślach) obieg post/pre/in- fixowy dla powyższego drzewa BST.
Jak zawsze zachęcam do komentowania, dyskutowania i zadawania pytań!
3 komentarze
Rekomendowane komentarze