Drzewo (matematyka)
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Drzewo – oznacza w teorii grafów graf, który jest acykliczny i spójny. Mówiąc językiem obrazowym, z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, czyli brak możliwości chodzenia w "kółko").
Spis treści |
[edytuj] Równoważne definicje
Graf prosty G jest jest drzewem jedynie, jeśli 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
[edytuj] Przykłady drzew
 |
 |
 |
 |
[edytuj] 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ącą się od korzenia i zawierające 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.
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 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.
[edytuj] Zastosowanie drzew
[edytuj] Diagramy zależności
W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), zależności typu klient-serwer czy zbioru uporządkowanego (diagram Hassego).
[edytuj] 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 struktury 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
[edytuj] 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.
[edytuj] Własności drzew
W drzewie ukorzenionym istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem, na rys. przykładowa droga do węzła J jest zaznaczona na czerwono. 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 to największy poziom istniejący w drzewie (przykładowe drzewo ma wysokość 4).
