Drzewa jako szczególny rodzaj grafów

2.1 Podstawowe komponenty drzewa

Drzewo to specjalny rodzaj grafu, który jest acykliczny i spójny. W drzewie istnieje jedyna ścieżka pomiędzy dowolną parą węzłów, co czyni jego strukturę hierarchiczną.

Podstawowe komponenty drzewa:

1. Węzły:

• Podstawowe elementy drzewa, które zawierają dane.
• Na przykład, każdy okrąg na diagramie reprezentuje węzeł.

2. Korzeń:

• Węzeł, który nie ma rodzicielskich węzłów. Jest punktem początkowym drzewa.
• Na przykład, górny węzeł na diagramie.

3. Liście:

• Węzły, które nie mają potomnych węzłów. Znajdują się na "końcach" drzewa.
• Na przykład, węzły na dole diagramu.

4. Krawędzie:

• Połączenia pomiędzy węzłami. Określają relacje rodzic-potomek pomiędzy węzłami.
• Na przykład, linie łączące węzły na diagramie.

5. Poddrzewa:

• Dowolny podzbiór drzewa składający się z węzła i wszystkich jego potomków.
• Na przykład, gałąź drzewa wychodząca z jednego węzła.

Ważne cechy drzewa:

1. Wysokość drzewa:

• Długość ścieżki od korzenia do najdalszego liścia.
• Na przykład, liczba poziomów na diagramie.

2. Głębokość węzła:

• Długość ścieżki od korzenia do danego węzła.
• Na przykład, liczba poziomów od korzenia do konkretnego węzła.

2.2 Drzewa binarne

Można wyróżnić różne rodzaje drzew. Zaczniemy od tych najprostszych.

Drzewo binarne to drzewo, w którym każdy węzeł ma nie więcej niż dwóch potomnych węzłów, nazywanych lewym i prawym potomkiem.

Przykład drzewa binarnego:

Specjalne rodzaje drzew binarnych:

Pełne drzewo binarne:

Wszystkie poziomy drzewa, poza ostatnim, są w pełni wypełnione, a wszystkie węzły ostatniego poziomu są umieszczone jak najbardziej z lewej strony.

Doskonale drzewo binarne:

Wszystkie wewnętrzne węzły mają dokładnie dwóch potomnych węzłów, a wszystkie liście znajdują się na tym samym poziomie.

Zrównoważone drzewo binarne:

Różnica wysokości poddrzew dowolnego węzła nie przekracza 1.

Drzewo binarne wyszukiwania:

Dla dowolnego węzła jego lewe poddrzewo zawiera tylko węzły z mniejszymi wartościami, a prawe poddrzewo – tylko węzły z większymi wartościami.

2.3 Drzewa n-arnych

Drzewo n-arne to drzewo, w którym każdy węzeł może mieć nie więcej niż n potomnych węzłów.

Specjalne rodzaje drzew n-arnych:

1. Drzewo ternarne (Ternary Tree):

Każdy węzeł ma nie więcej niż trzech potomnych węzłów.

2. Drzewo k-arne (k-ary Tree):

Każdy węzeł ma nie więcej niż k potomnych węzłów.

Przykład drzewa 3-arnego (każdy węzeł ma nie więcej niż trzech potomnych węzłów):

2.4 Przykłady zastosowania drzew

1. System plików

Zastosowanie drzew: Przedstawienie hierarchicznej struktury plików i folderów w systemie operacyjnym.

Korzeń reprezentuje katalog główny, węzły wewnętrzne — foldery, a liście — pliki. Operacje obejmują tworzenie, usuwanie i przenoszenie plików oraz folderów.

2. Drzewo decyzyjne

Zastosowanie drzew: Analiza i uczenie maszynowe do podejmowania decyzji.

Węzły wewnętrzne reprezentują pytania lub warunki, gałęzie — możliwe odpowiedzi, a liście — ostateczne decyzje lub działania. Na przykład, diagnostyka chorób w medycynie na podstawie objawów.

3. Dokument XML/HTML

Zastosowanie drzew: Strukturalne przedstawienie danych w formacie XML lub HTML.

Korzeń reprezentuje cały dokument, węzły wewnętrzne — tagi i elementy, a liście — węzły tekstowe i atrybuty. To pomaga w parsowaniu i manipulacji zawartością dokumentów.

4. Struktura organizacyjna

Zastosowanie drzew: Przedstawienie hierarchii w organizacjach i firmach.

Korzeń reprezentuje dyrektora generalnego, węzły wewnętrzne — menedżerów i działy, a liście — pracowników. To pomaga wizualizować i zarządzać strukturą organizacyjną.

5. Gra w szachy

Zastosowanie drzew: Przedstawienie możliwych ruchów w grze.

Korzeń reprezentuje początkowy stan gry, węzły wewnętrzne — możliwe ruchy, a liście — ostateczne stany gry. To pomaga w planowaniu strategii i podejmowaniu decyzji w programach szachowych.