Sortowanie stogowe

Drzewo (ang. tree) jest strukturą danych zbudowaną z elementów, które nazywamy węzłami (ang. node). Dane przechowuje się w węzłach drzewa. Węzły są ze sobą powiązane w sposób hierarchiczny za pomocą krawędzi (ang. edge), które zwykle przedstawia się za pomocą strzałki określającej hierarchię. Pierwszy węzeł drzewa nazywa się korzeniem (ang. root node). Od niego "wyrastają" pozostałe węzły, które będziemy nazywać synami (ang. child node). Synowie są węzłami podrzędnymi w strukturze hierarchicznej. Synowie tego samego ojca są nazywani braćmi (ang. sibling node). Węzeł nadrzędny w stosunku do syna nazwiemy ojcem (ang. parent node). Ojcowie są węzłami nadrzędnymi w strukturze hierarchicznej. Jeśli węzeł nie posiada synów, to nazywa się liściem (ang. leaf node), w przeciwnym razie nazywa się węzłem wewnętrznym (ang. internal node, inner node, branch node).

Struktura drzewa
		A...H – węzły drzewa strzałki – krawędzie. Zwrot określa kierunek hierarchii rodzić → dziecko. A – korzeń drzewa B,C,D  – bracia, synowie węzła A, który jest dla nich ojcem E,F,G  – bracia, synowie węzła B, który jest dla nich ojcem H – syn węzła D, który jest dla niego ojcem A,B,D – węzły wewnętrzne C,E,F,G,H – liście

 

Za wyjątkiem korzenia wszystkie pozostałe węzły w drzewie posiadają swojego ojca. W normalnym drzewie liczba synów dla dowolnego węzła nie jest ograniczona. Istnieje jednakże bardzo ważna klasa drzew, w których dany węzeł może posiadać co najwyżej dwóch synów. Noszą one nazwę drzew binarnych (ang. binary tree).

Ciąg węzłów połączonych krawędziami nazwiemy ścieżką (ang. path). Od korzenia do określonego węzła w drzewie wiedzie zawsze dokładnie jedna ścieżka prosta, tzn. taka, iż zawarte w niej węzły pojawiają się tylko jeden raz. Długością ścieżki (ang. path length) nazwiemy liczbę krawędzi łączących węzły w ścieżce. Dla naszego drzewa mamy następujące ścieżki proste od korzenia do kolejnych węzłów:

Struktura drzewa		Ścieżki
		ścieżka od A do A: długość 0: A ścieżka od A do B: długość 1: A→B ścieżka od A do C: długość 1: A→C ścieżka od A do D: długość 1: A→D ścieżka od A do E: długość 2: A→B→E ścieżka od A do F: długość 2: A→B→F ścieżka od A do G: długość 2: A→B→G ścieżka od A do H: długość 2: A→D→H

 

Długość ścieżki prostej od korzenia do danego węzła nazywa się poziomem węzła (ang. node level). Korzeń drzewa ma zawsze poziom 0. W naszym drzewie węzły B, C i D mają poziom 1, a E, F, G i H mają poziom 2. Wysokość drzewa (ang. tree height) jest równa największemu poziomowi węzłów (lub najdłuższej ścieżce rozpoczynającej się w korzeniu). Dla naszego drzewa wysokość jest równa 2. Wysokość węzła (ang. node height), to długość najdłuższej ścieżki od tego węzła do liścia. Dla korzenia wysokość węzła jest równa wysokości drzewa:

Struktura drzewa		Wysokości węzłów
		węzeł A: wysokość = 2 węzeł B: wysokość = 1 węzeł C: wysokość = 0 węzeł D: wysokość = 1 węzeł E: wysokość = 0 węzeł F: wysokość = 0 węzeł G: wysokość = 0 węzeł H: wysokość = 0

 

Poziom drzewa (ang. tree level, the level of a tree) dla danego węzła to długość ścieżki prostej od korzenia do danego węzła.

Struktura drzewa		Poziomy
		Poziom 0: A Poziom 1: B,C,D Poziom 2: E,F,G,H

 

Drzewo, w którym węzły mogą posiadać co najwyżej dwóch synów, nazywa się drzewem binarnym (ang. binary tree, B-tree). Węzły potomne nazywamy odpowiednio synem lewym (ang. left child node) i synem prawym (ang. right child node). Drzewa binarne mają ogromne znaczenie w informatyce, ponieważ za ich pomocą można odwzorować również drzewa, których węzły posiadają dowolną liczbę synów – sposób takiego odwzorowania podamy w dalszej części rozdziału.

Drzewo binarne
		A – korzeń, ojciec B i C B,C – synowie A, B – lewy syn A, C – prawy syn A D,E – liście, synowie B F,G – liście, synowie C

 

W drzewie binarnym stopień każdego węzła nie przekracza 3. Stopień korzenia nie przekracza 2.

Regularne drzewo binarne (ang. regular binary tree, proper binary tree) zawiera wyłącznie węzły, których stopień wyjściowy jest albo równy 2 (węzeł posiada dwóch synów – jest węzłem wewnętrznym), albo 0 (węzeł nie posiada synów – jest liściem).

Regularne drzewo binarne		Stopnie wyjściowe
		A – stopień wyjściowy 2, węzeł wewnętrzny B – stopień wyjściowy 2, węzeł wewnętrzny C – stopień wyjściowy 2, węzeł wewnętrzny D – stopień wyjściowy 0, liść E – stopień wyjściowy 0, liść F – stopień wyjściowy 0, liść G – stopień wyjściowy 0, liść

 

Dla regularnego drzewa binarnego liczba węzłów na poziomie k-tym jest zawsze równa 2^k.  Liczba wszystkich węzłów, czyli rozmiar drzewa (ang. binary tree size) jest równa 2^p - 1, gdzie p oznacza liczbę poziomów.

 

Dla n  węzłów liczba poziomów jest równa log₂(n+1).

Ponumerujmy poziomami kolejne węzły, idąc od strony lewej do prawej:

 

Otrzymane numery węzłów są powiązane ze strukturą hierarchii drzewa prostymi zależnościami:

		Jeśli węzeł o numerze k  posiada synów, to: lewy syn ma numer 2k+1 prawy syn ma numer 2k+2
		Jeśli węzeł o numerze k posiada ojca, to: ojciec ma numer [(k-1) / 2] [...] oznacza część całkowitą.

 

Węzeł o numerze k  znajduje się na poziomie o numerze [log₂(k+1)].

Węzeł o numerze k  jest wewnętrzny, jeśli 2k+2 < n. W przeciwnym razie węzeł jest liściem.

Własności te pozwalają odwzorowywać regularne drzewo binarne w ciąg elementów i na odwrót

 

 

Kompletne drzewo binarne (ang. complete binary tree) posiada zapełnione węzłami wszystkie poziomy z wyjątkiem ostatniego, jednakże na ostatnim poziomie węzły są zapełnione począwszy od lewej strony.

 

Kompletne drzewo binarne		Niekompletne drzewo binarne

 

Kompletne drzewo binarne również da się odwzorować w ciąg węzłów. W takim drzewie liczba elementów n może być mniejsza od maksymalnej liczby węzłów, ponieważ ostatni poziom nie musi posiadać kompletu węzłów. Jednakże w przeciwieństwie do drzewa regularnego węzeł wewnętrzny może posiadać tylko jednego, lewego syna (u nas węzłem takim jest węzeł 4). Dlatego w kompletnym drzewie binarnym o rozmiarze n  dla węzła o numerze k  zachodzi:

 

 

Poddrzewo (ang. subtree) jest drzewem zawartym w drzewie, gdy jako korzeń przyjmiemy jeden z węzłów. Dla danego węzła drzewa binarnego mogą istnieć dwa poddrzewa: lewe poddrzewo (ang. left subtree) – korzeniem jest lewy syn i analogicznie prawe poddrzewo (ang. right subtree) – korzeniem jest prawy syn: