Wprowadzenie do drzew

Treeto dyskretna struktura reprezentująca hierarchiczne relacje między poszczególnymi elementami lub węzłami. Drzewo, w którym rodzic ma nie więcej niż dwoje dzieci, nazywane jest drzewem binarnym.

Drzewo i jego właściwości

Definition- Drzewo jest połączonym, acyklicznym, niekierowanym grafem. Między każdą parą wierzchołków w $ G $ istnieje unikalna ścieżka. Drzewo z liczbą N wierzchołków zawiera $ (N-1) $ liczbę krawędzi. Wierzchołek, który ma 0 stopni, nazywany jest korzeniem drzewa. Wierzchołek, który ma 1 stopień, nazywany jest węzłem liścia drzewa, a stopień węzła wewnętrznego wynosi co najmniej 2.

Example - Poniżej przedstawiono przykład drzewa -

Centra i Bi-Centra drzewa

Środek drzewa to wierzchołek o minimalnej ekscentryczności. Mimośrodowość wierzchołka $ X $ w drzewie $ G $ to maksymalna odległość między wierzchołkiem $ X $ a jakimkolwiek innym wierzchołkiem drzewa. Maksymalna mimośrodowość to średnica drzewa. Jeśli drzewo ma tylko jedno centrum, nazywa się je drzewem centralnym, a jeśli drzewo ma tylko więcej niż jeden środek, nazywa się je drzewem dwu-centralnym. Każde drzewo jest centralne lub dwu-centralne.

Algorytm znajdowania środków i dwucentrów drzewa

Step 1 - Usuń wszystkie wierzchołki stopnia 1 z danego drzewa, a także usuń ich krawędzie.

Step 2- Powtarzaj krok 1, aż zostanie pojedynczy wierzchołek lub dwa wierzchołki połączone krawędzią. Jeśli pozostawiony zostanie pojedynczy wierzchołek, jest to środek drzewa, a jeśli dwa wierzchołki połączone krawędzią zostaną pozostawione, to jest to środek drzewa.

Problem 1

Znajdź środek / dwuśrodek następującego drzewa -

Solution

Najpierw usuniemy wszystkie wierzchołki stopnia 1, a także usuniemy ich krawędzie padające i otrzymamy następujące drzewo -

Ponownie usuniemy wszystkie wierzchołki stopnia 1, a także usuniemy ich krawędzie padające i otrzymamy następujące drzewo -

W końcu mamy pojedynczy wierzchołek „c” i zatrzymujemy algorytm. Ponieważ istnieje pojedynczy wierzchołek, drzewo to ma jeden środek „c”, a drzewo jest drzewem centralnym.

Problem 2

Znajdź środek / dwuśrodek następującego drzewa -

Solution

Najpierw usuniemy wszystkie wierzchołki stopnia 1, a także usuniemy ich krawędzie padające i otrzymamy następujące drzewo -

Ponownie usuniemy wszystkie wierzchołki stopnia 1, a także usuniemy ich krawędzie padające i otrzymamy następujące drzewo -

Ostatecznie mamy dwa wierzchołki „c” i „d” w lewo, dlatego zatrzymujemy algorytm. Ponieważ lewe są dwa wierzchołki połączone krawędzią, drzewo to ma dwuśrodkowe „cd”, a drzewo jest dwuśrodkowe.

Oznaczone drzewa

Definition- Drzewo etykietowane to drzewo, którego wierzchołki mają przypisane unikalne liczby od 1 do n. Możemy ręcznie policzyć takie drzewa dla małych wartości n, aby przypuszczać ogólny wzór. Liczba oznaczonych drzew o n liczbie wierzchołków wynosi $ n ^ {n-2} $. Dwa oznakowane drzewa są izomorficzne, jeśli ich wykresy są izomorficzne, a odpowiadające im punkty obu drzew mają takie same etykiety.

Przykład

Drzewa bez etykiety

Definition- Drzewo bez etykiety to drzewo, którego wierzchołkom nie przypisano żadnych liczb. Liczba oznaczonych drzew z n liczby wierzchołków wynosi $ \ frac {(2n)!} {(N + 1)! N! } $ (n- ^ty numer kataloński)

Przykład

Ukorzenione drzewo

Drzewo z korzeniami $ G $ jest połączonym grafem acyklicznym ze specjalnym węzłem nazywanym korzeniem drzewa, a każda krawędź bezpośrednio lub pośrednio pochodzi z korzenia. Uporządkowane drzewo ukorzenione to drzewo zakorzenione, w którym uporządkowane są dzieci każdego wewnętrznego wierzchołka. Jeśli każdy wewnętrzny wierzchołek zakorzenionego drzewa ma nie więcej niż m dzieci, nazywa się je drzewem m-arnym. Jeśli każdy wewnętrzny wierzchołek zakorzenionego drzewa ma dokładnie m dzieci, nazywane jest pełnym drzewem m-arnym. Jeśli $ m = 2 $, zakorzenione drzewo nazywane jest drzewem binarnym.

Drzewo wyszukiwania binarnego

Drzewo wyszukiwania binarnego jest drzewem binarnym, które spełnia następującą właściwość -

• $ X $ w lewym poddrzewie wierzchołka $ V, Wartość (X) \ le Wartość (V) $
• $ Y $ w prawym poddrzewie wierzchołka $ V, Wartość (Y) \ ge Wartość (V) $

Zatem wartość wszystkich wierzchołków lewego poddrzewa wewnętrznego węzła $ V $ jest mniejsza lub równa $ V $, a wartość wszystkich wierzchołków prawego poddrzewa wewnętrznego węzła $ V $ są większe lub równe $ V $. Liczba łączy od węzła głównego do najgłębszego to wysokość drzewa wyszukiwania binarnego.

Przykład

Algorytm wyszukiwania klucza w BST

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)

Złożoność drzewa wyszukiwania binarnego

	Średnia wielkość	Najgorszy przypadek
Złożoność przestrzeni	Na)	Na)
Wyszukaj złożoność	O (log n)	Na)
Złożoność wstawiania	O (log n)	Na)
Złożoność usuwania	O (log n)	Na)