Drzewo binarne

W informatyce , o drzewo binarne jest strukturą danych , które można przedstawić w formie hierarchii z których każdy element nazywa się węzeł początkowy węzeł miano korzeń . W drzewie binarnym każdy element ma najwyżej dwa elementy potomne na niższym poziomie, zwykle nazywane left i right . Z punktu widzenia tych elementów potomnych, element, z którego wywodzą się one na wyższy poziom, nazywany jest ojcem .

Na najwyższym poziomie, poziomie 0, znajduje się węzeł główny. Na poziomie bezpośrednio poniżej znajdują się co najwyżej dwa węzły podrzędne. Kontynuując schodzenie na niższe poziomy, można mieć cztery, potem osiem, szesnaście itd. to znaczy kolejność potęg dwójki . Węzeł bez dzieci nazywamy liściem .

Poziom węzła, innymi słowy odległość między tym węzłem a korzeniem, nazywana jest głębokością . Wysokość drzewa jest maksymalna głębokość węzła. Drzewo zredukowane do pojedynczego węzła ma wysokość 1.

Drzewa binarne mogą w szczególności być używane jako drzewo wyszukiwania binarnego lub jako sterta binarna .

Definicja w teorii grafów

Teorii wykres stosuje następującą definicję: drzewo binarne jest połączony wykres acykliczne , takie jak stopień każdego węzła (lub wierzchołek) wynosi co najwyżej 3.

Korzeń drzewa binarnego jest węzłem grafu o maksymalnym stopniu 2. Przy tak wybranym korzeniu, każdy węzeł będzie miał unikalnego, zdefiniowanego rodzica i dwoje dzieci; jednak ta informacja jest niewystarczająca, aby odróżnić prawego syna od lewego syna. Jeśli zaniedbamy ten warunek połączenia, a istnieje wiele połączonych elementów, nazwiemy tę strukturę lasem.

Rodzaje drzew binarnych

• Binarny (lub binarnie jednoskładnikowa) drzewo to drzewo z korzeniem w którym każdy węzeł ma co najwyżej dwoje dzieci.
• Surowe lub lokalnie kompletne drzewo binarne to drzewo, w którym wszystkie węzły mają zero lub dwoje dzieci.
• Zdegenerowane drzewo binarne to drzewo, w którym wszystkie wewnętrzne węzły mają tylko jedno dziecko. Ten typ drzewa ma tylko jeden liść i może być widziany jako lista połączona.
• Idealne drzewo binarne jest surowe drzewo binarne, w którym wszystkie liście (węzły bez dzieci) są w takiej samej odległości od korzenia (czyli tej samej głębokości). Jest to drzewo z wypełnionymi wszystkimi poziomami: gdzie wszystkie węzły wewnętrzne mają dwoje dzieci i gdzie wszystkie węzły zewnętrzne mają tę samą wysokość.
• Kompletne lub prawie kompletne drzewo binarne , którego nie należy mylić z lokalnie kompletnym (powyżej), to drzewo, w którym wszystkie poziomy są wypełnione z możliwym wyjątkiem ostatniego, w którym liście są wyrównane do lewej. Widzimy w nim doskonałe drzewo, którego ostatni poziom zostałby pozbawiony niektórych liści, zaczynając od najbardziej prawego. Innym sposobem spojrzenia na to byłoby ścisłe drzewo binarne, w którym liście mają głębokość n lub n-1 dla danego n . Ewentualność jest ważna: doskonałe drzewo jest z konieczności prawie kompletne, podczas gdy prawie kompletne drzewo może być doskonałe.

Istnieją sprzeczne zastosowania terminów kompletny i doskonały , które mogą być używane w sposób opisany powyżej, ale czasami mogą być zamieniane. Może to powodować zamieszanie lub nieporozumienia, dlatego możemy użyć terminu prawie kompletne w odniesieniu do drzewa na ostatnim, prawdopodobnie niewypełnionym poziomie. Mogą również istnieć pomyłki między francuskim a angielskim, w których znajdujemy terminy doskonały i kompletny , ponownie z różnymi zastosowaniami w zależności od osoby.

Drzewa binarne mogą być konstruowane z prymitywów języka programowania na różne sposoby. W języku ze strukturami i wskaźnikami (lub referencjami ) drzewa binarne można zaprojektować, mając strukturę trójwęzłową, która zawiera pewne dane i wskaźniki do swojego prawego i lewego dziecka. Kolejność, którą to narzuca węzłom podrzędnym, jest czasami przydatna, w szczególności w przypadku tras infix. Czasami zawiera również wskaźnik do swojego jedynego rodzica. Jeśli węzeł ma mniej niż dwoje dzieci, jednemu z dwóch wskaźników można przypisać specjalną wartość zero; może również wskazywać na węzeł wartowniczy.

Drzewa binarne można również układać w tablice, a jeśli drzewo jest kompletnym drzewem binarnym, ta metoda nie marnuje miejsca, a wynikowe dane strukturalne są nazywane stertą . W tym zwartym układzie węzeł ma indeks i , a (tablica oparta na zerach) jego dzieci mają indeksy 2 i +1 oraz 2 i +2, natomiast jego ojciec (jeśli istnieje) ma indeks podłogi ( i-1) / 2) . Ta metoda umożliwia korzystanie z mniejszej powierzchni i lepszej referencji, w szczególności podczas skanowania prefiksów. Wymaga jednak ciągłej pamięci, jest to kosztowne, jeśli chodzi o rozszerzenie drzewa, a utracona przestrzeń (w przypadku niepełnego drzewa binarnego) jest proporcjonalna do 2 h - n dla drzewa o głębokości h z n węzłami .

W językach unii oznaczonych jako ML , węzeł jest często otagowaną unią dwóch typów węzłów, z których jeden jest trypletem zawierającym dane i jego prawe i lewe dzieci, a drugi jest pustym węzłem, który nie zawiera danych ani funkcji, przypominając wartość null języków ze wskaźnikami.

Metoda iteracji drzewa binarnego

Często pożądane jest odwiedzenie każdego z węzłów w drzewie i zbadanie tam wartości. Istnieje kilka porządków, w których można odwiedzać węzły, a każdy z nich ma przydatne właściwości, które są wykorzystywane przez algorytmy oparte na drzewie bitowym.

Ścieżka przedrostka, wrostka i przyrostka

(czasami nazywane preorder , inorder i postorder )

Rozważmy drzewo Atypu Arbre, root racine(A)i jego dwoje dzieci gauche(A)oraz droite(A). Możemy napisać następujące funkcje (zwróć uwagę na pozycję linii visiter (A)):

Prefiks trasy visiterPréfixe(Arbre A) : visiter (A) Si nonVide (gauche(A)) visiterPréfixe(gauche(A)) Si nonVide (droite(A)) visiterPréfixe(droite(A))

Spowoduje to wyświetlenie wartości drzewa w kolejności prefiksów. W tej kolejności odwiedzany jest każdy węzeł, a następnie każdy z jego dzieci.

Ścieżka przyrostka lub sufiksu visiterPostfixe(Arbre A) : Si nonVide(gauche(A)) visiterPostfixe(gauche(A)) Si nonVide(droite(A)) visiterPostfixe(droite(A)) visiter(A)

W ścieżce przyrostka lub przyrostka wyświetlamy każdy węzeł po wyświetleniu każdego z jego dzieci.

Kurs infiksowy visiterInfixe(Arbre A) : Si nonVide(gauche(A)) visiterInfixe(gauche(A)) visiter(A) Si nonVide(droite(A)) visiterInfixe(droite(A))

Spacer infix, jak powyżej, odwiedza każdy węzeł między węzłami jego lewego poddrzewa a węzłami jego prawego poddrzewa. Jest to dość powszechny sposób na iterację w drzewie wyszukiwania binarnego, ponieważ zwraca wartości w kolejności rosnącej.

Aby zrozumieć, dlaczego tak jest, jeśli n jest węzłem w drzewie wyszukiwania binarnego, wszystkie elementy w lewym poddrzewie węzła n będą mniejsze niż n, a te w prawym poddrzewie będą większe lub równe n . Tak więc, jeśli odwiedzimy lewe poddrzewo po kolei, rekursywnie, a następnie odwiedzimy n i odwiedzimy prawe poddrzewo, odwiedzimy całe zakorzenione poddrzewo w kolejności n .

W tym drzewie binarnym Renderowanie prefiksu trasy: 1, 2, 4, 5, 7, 8, 3, 6, 9 Renderuj ścieżkę postfix: 4, 7, 8, 5, 2, 9, 6, 3, 1 Renderowanie trasy infiksowej: 4, 2, 7, 5, 8, 1, 3, 9, 6 Renderowanie trasy w szerokości: 1, 2, 3, 4, 5, 6, 7, 8, 9

Możemy wykonać te trasy za pomocą funkcjonalnego języka, takiego jak Haskell, z następującym kodem:

data Tree a = Leaf | Node(a, Tree a, Tree a) preorder Leaf = [] preorder (Node (x, left,right)) = [x] ++ (preorder left) ++ (preorder right) postorder Leaf = [] postorder (Node (x, left,right)) = (postorder left) ++ (postorder right) ++ [x] inorder Leaf = [] inorder (Node (x, left,right)) = (inorder left) ++ [x] ++ (inorder right)

Wszystkie te algorytmy rekurencyjne wykorzystują stos pamięci proporcjonalny do głębokości drzew. Jeśli dodamy w każdym węźle odwołanie do jego rodzica, to możemy zaimplementować wszystkie te ścieżki, używając tylko stałych przestrzeni pamięci i algorytmu iteracyjnego. Dużo miejsca zajmuje jednak odniesienie do rodzica; jest to naprawdę przydatne tylko wtedy, gdy jest to wymagane w inny sposób lub gdy stos pamięci jest szczególnie ograniczony. Oto na przykład iteracyjny algorytm ścieżki infiksowej:

VisiterInfixeIteratif(racine) precedent  := null actuel  := racine suivant  := null Tant que (actuel != null) Faire Si (precedent == pere(actuel)) Alors precedent := actuel suivant  := gauche(actuel) FinSi Si (suivant == null OU precedent == gauche(actuel)) Alors Visiter(actuel) precedent := actuel suivant  := droite(actuel) FinSi Si (suivant == null OU precedent == droite(actuel)) Alors precedent := actuel suivant  := pere(actuel) FinSi actuel := suivant FinTantQue

Kurs dogłębny

Podczas tego spaceru zawsze staramy się odwiedzić węzeł znajdujący się najdalej od roota, jaki możemy, pod warunkiem, że jest to dziecko węzła, który już odwiedziliśmy. W przeciwieństwie do dogłębnego przeglądania wykresów, nie trzeba wiedzieć, które węzły zostały już odwiedzone, ponieważ drzewo nie zawiera cykli. Trasy prefiksowe, infiksowe i postfiksowe są szczególnymi przypadkami tego typu trasy.

Aby wykonać tę podróż, konieczne jest prowadzenie listy przedmiotów oczekujących na przetworzenie. W przypadku przeglądania dogłębnego lista ta musi mieć strukturę stosu (typu LIFO, Last In, First Out, czyli „ostatnie weszło, pierwsze wyszło”). W tej implementacji zdecydujemy się również dodać dzieci węzła od prawej do lewej.

ParcoursProfondeur(Arbre A) { S = Pilevide ajouter(Racine(A), S) Tant que (S != Pilevide) { nœud = premier(S) retirer(S) Visiter(nœud) //On choisit de faire une opération Si (droite(nœud) != null) Alors ajouter(droite(nœud), S) Si (gauche(nœud) != null) Alors ajouter(gauche(nœud), S) } }

Kurs szerokości

W przeciwieństwie do poprzedniego, ten ślad zawsze próbuje odwiedzić węzeł najbliżej korzenia, który nie został jeszcze odwiedzony. Podążając tą trasą najpierw odwiedzimy root, potem węzły na głębokości 1, potem 2 itd. Stąd nazwa kurs na szerokość.

Implementacja jest prawie identyczna z trasą dogłębną, z tym wyjątkiem, że tym razem musimy użyć struktury kolejki (typ FIFO, First in, first out, innymi słowy „pierwsze weszło, pierwsze wyszło”) , co oznacza, że ​​kolejność wyjściowa to nie to samo (tj. zamieniamy lewą i prawą stronę w naszym przetwarzaniu).

ParcoursLargeur(Arbre A) { f = FileVide enfiler(Racine(A), f) Tant que (f != FileVide) { nœud = defiler(f) Visiter(nœud) //On choisit de faire une opération Si (gauche(nœud) != null) Alors enfiler(gauche(nœud), f) Si (droite(nœud) != null) Alors enfiler(droite(nœud), f) } }

Przekształcenie dowolnego drzewa w drzewo binarne

Istnieje wstrzyknięcie pomiędzy ogólnie posortowanymi drzewami a drzewami binarnymi, które jest specjalnie używane przez Lisp do przedstawiania ogólnie posortowanych drzew jako drzew binarnych. Każdy węzeł N w posortowanym drzewie odpowiada węzłowi N ' w drzewie binarnym; syn na lewo od N 'jest węzłem dla pierwszego syna N , a syn na prawo od N ' jest węzłem dla następnego brata N - który jest kolejnym węzłem w kolejności wśród dzieci ojca N .

Jednym ze sposobów na zobrazowanie tego jest myślenie, że każdy syn węzła na połączonej liście, każdy połączony przez swoje obowiązki pola , i że węzeł ma tylko wskaźnik na początek listy, do swojego lewego pola .

Na przykład w drzewie po lewej A ma 6 dzieci: {B, C, D, E, F, G}. Można go przekonwertować na drzewo binarne (jak to po prawej).

To drzewo binarne można traktować jako oryginalne drzewo pochylone na długość, z czarnymi bokami po lewej stronie przedstawiającymi pierwszych synów, a niebieskimi po prawej reprezentującymi kolejnych braci . Część drzewa po lewej można zakodować w Lispie w ten sposób:

(((MN) HI) CD ((O) (P)) F (L))

które mogą być zaimplementowane w pamięci jako prawe drzewo binarne, bez liter węzłów, które mają lewe dziecko.

Zobacz również

• Numer kataloński
• Numer Strahlera
• Algorytm Rémy'ego

Algorytmy wykorzystujące drzewa binarne

• Kodowanie Huffmana
• Algorytm węzła kapelusza

Poszczególne drzewa binarne

• Drzewo wyszukiwania binarnego
• Drzewo AVL
• Drzewo dwukolorowe (drzewo czerwono-czarne)
• Szyte drzewo

Inne rodzaje drzew

• Drzewo B
• drzewo BSP
• Drzewo trójskładnikowe  (w)

Uwagi i referencje