Drzewo – graf nieskierowany, który jest acykliczny[1] i spójny[2][1], czyli taki graf, w którym z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) tylko jednym sposobem (acykliczność, brak możliwości chodzenia „w kółko”)[3].
Równoważne definicje
[edytuj | edytuj kod]Graf prosty G jest drzewem jedynie wtedy, gdy spełnia jeden z warunków[3]:
- dowolne dwa wierzchołki łączy dokładnie jedna ścieżka prosta
- G jest acykliczny i dodanie krawędzi łączącej dowolne dwa wierzchołki utworzy cykl
- G jest spójny i usunięcie dowolnej krawędzi spowoduje, że G przestanie być spójny
Przykłady drzew
[edytuj | edytuj kod]Terminologia
[edytuj | edytuj kod]Drzewo, w którym jest wyróżniony jeden z wierzchołków, nazywamy drzewem ukorzenionym, a wyróżniony wierzchołek – korzeniem.
Na takim drzewie możemy również określić relacje „rodzinne” pomiędzy wierzchołkami.
Dla dowolnej ścieżki prostej rozpoczynającej się od korzenia i zawierającej wierzchołek v:
- wierzchołki występujące w ścieżce przed v nazywamy jego przodkami v, a wierzchołki występujące po v – potomkami,
- wierzchołek bezpośrednio przed v nazywamy rodzicem lub ojcem, a bezpośrednio po – dzieckiem lub synem,
- wierzchołki mające wspólnego ojca nazywamy braćmi.
Wierzchołki, które nie mają synów, nazywamy liśćmi drzewa.
Najdłuższą ścieżkę w drzewie nazywamy średnicą drzewa. Jej długość liczymy, stosując programowanie dynamiczne.
W informatyce bardzo często wymaga się, żeby synowie tworzyli nie zbiór, lecz listę uporządkowaną. Taki twór co prawda nie jest matematycznie grafem, jednak ma ogromne znaczenie w tej dziedzinie matematyki.
Graf prosty, acykliczny i niespójny, który można traktować jako zbiór drzew, nazywa się lasem.
Podstawowe operacje na drzewach to:
- wyliczenie wszystkich elementów drzewa,
- wyszukanie konkretnego elementu,
- dodanie nowego elementu w określonym miejscu drzewa,
- usunięcie elementu.
Zastosowanie drzew
[edytuj | edytuj kod]Diagramy zależności
[edytuj | edytuj kod]W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć itp.) lub zależności typu klient-serwer.
Struktury danych
[edytuj | edytuj kod]W informatyce wiele struktur danych jest konkretną realizacją drzewa matematycznego. Wierzchołki drzewa reprezentują konkretne dane (liczby, napisy albo bardziej złożone struktury danych). Odpowiednie ułożenie danych w drzewie może ułatwić i przyspieszyć ich wyszukiwanie. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. algorytmika, kryptografia, bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).
Specjalne znaczenie w informatyce mają drzewa binarne (liczba dzieci ograniczona do dwóch) i ich różne odmiany, np. drzewa AVL, drzewa czerwono-czarne, BST; drzewa, które posiadają więcej niż dwoje dzieci, są nazywane drzewami wyższych rzędów.
Zobacz też: Kopiec, Kodowanie Huffmana
Inne
[edytuj | edytuj kod]Jako drzewa przedstawia się składnie języków formalnych, w tym rachunku lambda. W teorii gier występują drzewa decyzyjne. Bazy danych i systemy plików stosują wiele algorytmów opartych na drzewach i specjalnych postaciach drzew takich jak drzewa binarne, B drzewa, B+ drzewa, drzewa AVL i inne.
Własności drzew
[edytuj | edytuj kod]W grafie gdzie to zbiór wierzchołków grafu, a to zbiór krawędzi. Następujące warunki są równoważne:
- jest drzewem
- dla każdych dwóch wierzchołków w grafie istnieje dokładnie jedna uv-ścieżka
- jest spójny i
- jest acykliczny i
W drzewie ukorzenionym istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem. Liczba krawędzi w ścieżce jest nazywana długością (lub głębokością) – liczba o jeden większa określa poziom węzła. Z kolei wysokość drzewa jest równa wysokości jego korzenia, czyli długości najdłuższej ścieżki prostej od korzenia do liścia[4][5].
Liczba oznaczonych drzew o wierzchołkach wynosi:
Formuła ta nosi nazwę wzoru Cayleya.
Liczba drzew na zbiorze -wierzchołków (gdzie jest większe bądź równe 2), z których każdy ma stopień a suma stopni to wynosi:
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ a b Słownik terminologiczny informacji naukowej, Maria Dembowska, Wrocław–Warszawa–Kraków–Gdańsk: Zakład Narodowy imienia Ossolińskich, 1979, s. 40 .
- ↑ graf, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-03-10] .
- ↑ a b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 12. ISBN 0-387-95014-1.
- ↑ Thomas Cormen: Wprowadzenie do algorytmów. Wyd. 8. Wydawnictwa Naukowo-Techniczne, 2007, s. 1114. ISBN 978-83-204-3328-9.
- ↑ Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2006, s. 34. ISBN 83-204-3224-3.
Linki zewnętrzne
[edytuj | edytuj kod]- Eric W. Weisstein , Tree, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).