Drzewo (matematyka)

Ten artykuł dotyczy znaczenia drzewa w matematyce. Zobacz też: inne znaczenia.

Drzewo – graf nieskierowany, który jest acykliczny^[1] i spójny^[2][1], czyli taki graf, że z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, brak możliwości chodzenia „w kółko”)^[3].

Graf prosty G jest drzewem jedynie, jeśli 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

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.

W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć itp.) lub zależności typu klient-serwer.

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

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 grafie ${\displaystyle G=(V,E),}$ gdzie ${\displaystyle V}$ to zbiór wierzchołków grafu, a ${\displaystyle E}$ to zbiór krawędzi. Następujące warunki są równoważne:

1. ${\displaystyle G}$ jest drzewem
2. dla każdych dwóch wierzchołków ${\displaystyle u,v\in V}$ w grafie ${\displaystyle G}$ istnieje dokładnie jedna uv-ścieżka
3. ${\displaystyle G}$ jest spójny i ${\displaystyle |V|=|E|+1}$
4. ${\displaystyle G}$ jest acykliczny i ${\displaystyle |V|=|E|+1}$

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 ${\displaystyle n}$ wierzchołkach wynosi:

${\displaystyle n^{n-2}.}$

Formuła ta nosi nazwę wzoru Cayleya.

Liczba drzew na zbiorze ${\displaystyle n}$-wierzchołków (gdzie ${\displaystyle n}$ jest większe bądź równe 2), z których każdy ma stopień ${\displaystyle d_{1},d_{2},\dots ,d_{n},}$ a suma stopni to ${\displaystyle 2n-2,}$ wynosi:

${\displaystyle {n-2 \choose d_{1}-1,d_{2}-1,\dots ,d_{n}-1}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\ldots (d_{n}-1)!}}.}$

Zobacz hasło drzewo w Wikisłowniku

• drzewo jako struktura danych w informatyce
• drzewo rozpinające
• teoria grafów

• Eric W.E.W. Weisstein Eric W.E.W., Tree, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).