Drzewo – graf nieskierowany, który jest spójny i acykliczny, czyli: z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka – spójność; można to zrobić tylko jednym sposobem – acykliczność, czyli brak możliwości chodzenia „w kółko”.
Równoważne definicje Graf prosty G jest drzewem jedynie wtedy, gdy spełnia jeden z warunków: 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
Terminologia 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 Diagramy zależności W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć itp.) lub zależności typu klient-serwer.
Struktury danych 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 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 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.
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ż
drzewo jako struktura danych w informatyce drzewo rozpinające teoria grafów
Przypisy
Linki zewnętrzne Oskar Skibski, Drzewa [w:] Matematyka Dyskretna, kanał autorski na YouTube, 17 kwietnia 2020 [dostęp 2026-01-17] – nagranie w ramach kursu, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW).
Tree , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-12].
Kategoria:Klasy grafów