W tym samouczku dowiesz się o strukturze danych drzewa. Dowiesz się również o różnych typach drzew i terminologii używanej w drzewie.
Drzewo to nieliniowa hierarchiczna struktura danych, która składa się z węzłów połączonych krawędziami.
Drzewo
Dlaczego struktura danych drzewa?
Inne struktury danych, takie jak tablice, połączona lista, stos i kolejka, to liniowe struktury danych, które przechowują dane sekwencyjnie. Aby wykonać dowolną operację w liniowej strukturze danych, złożoność czasowa rośnie wraz ze wzrostem rozmiaru danych. Jednak w dzisiejszym świecie obliczeń jest to nie do przyjęcia.
Różne drzewiaste struktury danych umożliwiają szybszy i łatwiejszy dostęp do danych, ponieważ jest to nieliniowa struktura danych.
Drzewo Terminologie
Węzeł
Węzeł to jednostka zawierająca klucz lub wartość i wskaźniki do jego węzłów podrzędnych.
Ostatnie węzły każdej ścieżki nazywane są węzłami-liśćmi lub węzłami zewnętrznymi , które nie zawierają łącza / wskaźnika do węzłów podrzędnych.
Węzeł mający co najmniej węzeł podrzędny nazywany jest węzłem wewnętrznym .
Brzeg
Jest to łącze między dowolnymi dwoma węzłami.
Węzły i krawędzie drzewa
Korzeń
Jest to najwyższy węzeł drzewa.
Wysokość węzła
Wysokość węzła to liczba krawędzi od węzła do najgłębszego liścia (tj. Najdłuższa ścieżka od węzła do węzła liścia).
Głębokość węzła
Głębokość węzła to liczba krawędzi od podstawy do węzła.
Wysokość drzewa
Wysokość drzewa to wysokość węzła głównego lub głębokość najgłębszego węzła.
Wysokość i głębokość każdego węzła w drzewie
Stopień węzła
Stopień węzła to całkowita liczba gałęzi tego węzła.
Las
Zbiór rozłącznych drzew nazywany jest lasem.
Tworzenie lasu z drzewa
Możesz stworzyć las, wycinając korzeń drzewa.
Rodzaje drzew
- Drzewo binarne
- Drzewo wyszukiwania binarnego
- Drzewo AVL
- B-Tree
Tree Traversal
Aby wykonać jakąkolwiek operację na drzewie, musisz dotrzeć do konkretnego węzła. Algorytm przechodzenia po drzewie pomaga w odwiedzaniu żądanego węzła w drzewie.
Aby dowiedzieć się więcej, odwiedź stronę poświęconą przemierzaniu drzew.
Aplikacje w drzewie
- Binarne drzewa wyszukiwania (BST) służą do szybkiego sprawdzania, czy element jest obecny w zestawie, czy nie.
- Sterta to rodzaj drzewa używanego do sortowania sterty.
- Zmodyfikowana wersja drzewa o nazwie Tries jest używana w nowoczesnych routerach do przechowywania informacji o routingu.
- Większość popularnych baz danych używa B-Drzewa i T-Drzewa, które są wariantami struktury drzewiastej, której nauczyliśmy się powyżej, do przechowywania danych
- Kompilatory używają drzewa składni do sprawdzania poprawności składni każdego napisanego programu.
