5270659536

Drzewa

Drzewa to rodzaj struktury danych, w której możemy wyróżnić:

>    korzeń (wierzchołek główny) - nie ma rodzica/przodka

>    wierzchołki (wewnętrzne) (węzły), które połączone są krawędziami i mogą posiadać:

■    poprzedniki (przodków, rodziców - bezpośrednie poprzedniki)

■    następniki (potomków, dzieci - bezpośrednie następniki)

>• liście (nie posiadają już następników)

Każdy wierzchołek może posiadać dowolną ilość dzieci:

■    drzewa binarne posiadają maksymalnie dwa

■    drzewa wyższych rzędów (np. AVL, czerwono-czarne, BST) mogą posiadać więcej niż dwóch potomków

■    posiada dokładnie jednego rodzica

Ścieżka w drzewie - to droga (ciąg krawędzi) prowadząca między dowolnymi dwoma wierzchołkami w drzewie (istnieje zawsze tylko jedna)

Liczba krawędzi tworzących ścieżkę nazywana jest jej długością.

Poziom węzła w drzewie wyznacza 1+długość ścieżki łączącej korzeń drzewa z węzłem. Wysokość drzewa wyznaczona jest przez maksymalny poziom wszystkich jego węzłów. Las to kilka drzew powiązanych ze sobą razem.

Wykład 6. Strona 2.

PODSTAWY INFORMATYKI. Adrian Honzyk, http://home.agh.edu.pl/--horzyk