Drzewo (informatyka)

Z Wikipedii

W informatyce drzewa są strukturami danych reprezentującymi drzewa matematyczne. W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), toteż głównie do tego celu są stosowane. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. 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. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).

Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła (np. dziećmi wierzchołka D są G i H, wierzchołka H: J, K oraz L). Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem; na rysunku liście zaznaczone są kolorem niebieskim.

Wierzchołek jest rodzicem dla każdego swojego dziecka; każdy węzeł ma dokładnie jednego rodzica. Wyjątkiem jest korzeń drzewa, który nie ma rodzica.

W drzewie istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem; przez ścieżkę rozumie się ciąg krawędzi, na rys. przykładowa ścieżka do węzła J jest zaznaczona na czerwono. Liczba krawędzi w ścieżce jest nazywana długoś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).

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.

Podstawowe operacje na drzewach to:

• wyliczenie wszystkich elementów drzewa,
• wyszukanie konkretnego elementu,
• dodanie nowego elementu w określonym miejscu drzewa,
• usunięcie elementu.

Pod pojęciem przechodzenia drzewa rozumie się odwiedzanie kolejnych wierzchołków, zgodnie z zależnościami rodzic-dziecko. Jeśli przy przechodzeniu drzewa na wierzchołkach są wykonywane pewne działania, to mówi się wówczas o przechodzeniu:

• preorder - gdy działanie jest wykonywane najpierw na rodzicu, następnie na dzieciach;
• postorder - gdy działanie jest wykonywane najpierw na wszystkich dzieciach, na końcu na rodzicu.

W przypadku drzew binarnych istnieje jeszcze metoda inorder, gdzie najpierw wykonywane jest działanie na jednym z dzieci, następnie na rodzicu i na końcu na drugim dziecku.

Jeśli działaniem byłoby wypisanie liter przechowywanych w węzłach przykładowego drzewa, to przy przechodzeniu drzewa metodą preorder otrzymamy ABEFCDGIHJKL, natomiast przy przechodzeniu drzewa metodą postorder: EFBCIGJKLHDA.

Fizycznie drzewa są reprezentowane za pomocą struktur wiązanych – ogólnie pojedynczy wierzchołek przechowuje dane oraz dowiązania do swoich dzieci. W szczególności jeśli drzewo jest zapisane w tablicy (patrz: kopiec), to dzieci są wskazywani przez konkretne indeksy; jeśli drzewo jest budowane na stercie (w językach C, C++, Pascal i podobnych), wówczas dowiązania są wskaźnikami.

Przykład definicji typu drzewa, w którym dane występują tylko na liściach (ocaml):

type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree

Przykład definicji typu drzewa, w którym dane (napisy) występują na każdym węźle (C):

struct tree {
        struct tree *left;
        struct tree *right;
        char *dane;
};