Objaśnienie 4 rodzajów drzew w strukturze danych: właściwości i zastosowania

Co to jest drzewo w strukturze danych?

Drzewo to rodzaj struktury danych reprezentującej dane hierarchiczne. Ma nieliniową strukturę składającą się z węzłów połączonych krawędziami. Wśród innych typów struktur danych, które wykonują operacje na liniowej strukturze danych, złożoność wzrasta wraz ze wzrostem rozmiaru danych. Jednak struktura danych w postaci drzewa zapewnia szybszy dostęp do danych, co jest nieliniowe. Dzięki dostępności różnego rodzaju struktur danych i algorytmów z nimi związanych, wykonywanie zadań stało się łatwym i efektywnym sposobem.

Kilka terminów związanych z drzewami w strukturze danych to:

• Węzeł : węzeł jest jednostką w strukturze danych drzewa, która zawiera klucz lub wartość oraz wskaźniki do jego węzłów podrzędnych.
• Węzeł potomny : węzeł potomny jest potomkiem dowolnego węzła.
• Węzły liścia: węzły, które nie mają żadnych węzłów podrzędnych i są najniższym węzłem w drzewie. Nazywa się je również węzłami zewnętrznymi.
• Korzeń : to najwyższy punkt drzewa.
• Węzeł wewnętrzny : węzeł mający co najmniej jeden węzeł podrzędny.
• Krawędź: Krawędź odnosi się do połączenia między dowolnymi dwoma węzłami w drzewie.
• Wysokość węzła: Liczba krawędzi od węzła do najgłębszego liścia.
• Głębokość węzła : liczba krawędzi od nasady do węzła.
• Wysokość drzewa : Wysokość węzła głównego.
• Stopień węzła : Całkowita liczba gałęzi do tego węzła.
• Las: zbiór rozłącznych drzew.

Rodzaje drzew

1. Drzewo binarne

Drzewo binarne to rodzaj struktury danych drzewa, w którym każdy węzeł nadrzędny ma maksymalnie dwa węzły podrzędne. Jak sama nazwa wskazuje, binarny oznacza dwa, dlatego każdy węzeł może mieć 0, 1 lub 2 węzły. Strukturę danych w postaci drzewa binarnego pokazano na rysunku 1. Węzeł 1 w drzewie zawiera dwa wskaźniki, po jednym dla każdego węzła podrzędnego. Węzeł 2 ponownie ma po dwa wskaźniki dla dwóch węzłów podrzędnych. Podczas gdy węzły 3, 5 i 6 są węzłami typu liść i dlatego mają puste wskaźniki zarówno na lewej, jak i prawej części.

Rysunek 1: Reprezentacja drzewa binarnego ( https://www.javatpoint.com/binary-tree ).

Właściwości drzewa binarnego

• Maksymalna liczba węzłów na każdym poziomie I wynosi 2 i .
• Wysokość drzewa na rysunku 1 wynosi 3, co oznacza, że ​​maksymalna liczba węzłów będzie (1+2+4+8) =15.

• Na wysokości h maksymalna możliwa liczba węzłów to (20 + 21 + 22+….2h) = 2h+1 -1.

• Na wysokości h minimalna możliwa liczba węzłów jest równa h+1.

• Minimalna liczba węzłów będzie reprezentować drzewo o maksymalnej wysokości i na odwrót.

Nawet drzewa binarne można podzielić na następujące typy drzew:

• Pełne drzewo binarne: Jest to specjalny rodzaj drzewa binarnego. W tej drzewiastej strukturze danych każdy węzeł nadrzędny lub węzeł wewnętrzny ma albo dwoje podrzędnych, albo nie ma węzłów podrzędnych.
• Idealne drzewo binarne: w tego typu drzewiastej strukturze danych każdy węzeł wewnętrzny ma dokładnie dwa węzły podrzędne, a wszystkie węzły liści są na tym samym poziomie.
• Kompletne drzewo binarne: przypomina pełne drzewo binarne z kilkoma różnicami.
• Każdy poziom jest całkowicie wypełniony.
• Węzły liści pochylają się w lewo od drzewa.
• Ostatni węzeł-liść nie musi mieć odpowiedniego rodzeństwa, tzn. kompletne drzewo binarne nie musi być pełnym drzewem binarnym.
• Drzewo zdegenerowane lub patologiczne: te drzewa mają jedno dziecko po lewej lub prawej stronie węzła rodzica.
• Skośne drzewo binarne: Jest to drzewo patologiczne lub zdegenerowane, w którym dominują lewe lub prawe węzły. W związku z tym istnieją dwa rodzaje skośnych drzew binarnych, tj. drzewo binarne skośne lewostronnie lub drzewo binarne skośne prawostronnie.
• Zrównoważone drzewo binarne: różnica między wysokością lewego i prawego poddrzewa dla każdego węzła wynosi 0 lub 1.

2. Binarne drzewo wyszukiwania

Te struktury drzewiaste są nieliniowe, a jeden węzeł jest połączony z wieloma węzłami. Węzeł może być połączony z maksymalnie dwoma węzłami podrzędnymi. Nazywa się to drzewem wyszukiwania binarnego, ponieważ:

• Każdy węzeł ma maksymalnie dwa węzły podrzędne.
• Może być używany do wyszukiwania elementu w czasie 0(log(n)) i stąd znany jako drzewo wyszukiwania.

Rysunek: Przykład drzewa wyszukiwania binarnego ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Właściwości drzewa wyszukiwania binarnego to:

• Wartość we wszystkich węzłach lewego poddrzewa powinna być mniejsza niż wartość w węźle głównym.
• Wartość we wszystkich węzłach prawego poddrzewa powinna być większa niż wartość w węźle głównym.

3. Drzewo AVL

Drzewa AVL to typy lub warianty drzewa binarnego. Składa się z właściwości zarówno z binarnego, jak i binarnego drzewa wyszukiwania. Wynalezione przez Adelsona Velsky'ego Lindasa drzewa te są samobalansujące, co oznacza, że ​​wysokość lewego i prawego poddrzewa jest zrównoważona. Bilans ten jest mierzony za pomocą współczynnika równoważącego.

Współczynnik równoważenia:

• Jest to różnica między lewym poddrzewem a prawym poddrzewem.
• Wartość współczynnika równoważącego musi wynosić 0, -1 lub 1. Dlatego każdy węzeł drzewa AVL powinien składać się z wartości współczynnika równoważącego, tj. 0, -1 lub 1.
• Współczynnik równowagi = (wysokość lewego poddrzewa – wysokość prawego poddrzewa)
• O drzewie AVL mówi się, że jest drzewem zrównoważonym, jeśli współczynnik równowagi każdego węzła wynosi od -1 do 1.

Wartości węzłów inne niż -1 do 1 w drzewie AVL będą reprezentować niezrównoważone drzewo, które musi być zrównoważone.

• Jeśli węzeł ma współczynnik równowagi równy 1, oznacza to, że lewe poddrzewo jest o jeden poziom wyżej niż prawe poddrzewo.
• Jeśli węzeł ma współczynnik równowagi równy 0, oznacza to, że wysokość lewego poddrzewa i prawego poddrzewa jest równa.
• Jeśli węzeł ma współczynnik równowagi równy -1, oznacza to, że prawe poddrzewo jest o jeden poziom wyżej niż lewe poddrzewo lub lewe poddrzewo jest o jeden poziom niższe niż prawe poddrzewo.

4. B-drzewo

Drzewo B jest bardziej uogólnioną formą binarnego drzewa wyszukiwania. Jest również znane jako drzewo o zrównoważonej wysokości, gdzie m to rząd drzewa. Każdy węzeł drzewa może mieć więcej niż jeden klucz i więcej niż dwa węzły podrzędne. W przypadku drzewa binarnego węzły liści mogą nie znajdować się na tym samym poziomie. Jednak w przypadku drzewa B wszystkie węzły liści powinny znajdować się na tym samym poziomie.

Właściwości drzewa B:

• Klucze są przechowywane w porządku rosnącym dla każdego węzła x.
• W każdym węźle istnieje wartość logiczna „x.leaf”, co jest prawdą, jeśli x jest liściem.
• Węzły wewnętrzne powinny mieć co najwyżej „n-1” kluczy, gdzie n jest porządkiem drzewa. Powinien też mieć wskazówkę dla każdego dziecka.
• Wszystkie węzły będą miały co najwyżej n dzieci i co najmniej n/2 dzieci, z wyjątkiem węzła głównego.
• Węzły liściowe drzewa mają tę samą głębokość.
• Węzeł główny będzie miał co najmniej 1 klucz i co najmniej dwoje dzieci.
• Jeśli n ≥ 1, to dla dowolnego n-kluczowego drzewa B o wysokości h i minimalnym stopniu t ≥ 2, h ≥ logt (n+1)/2.

Aplikacje

• Drzewo wyszukiwania binarnego można zastosować do wyszukiwania elementu w zestawie elementów.
• Drzewa sterty są używane do sortowania sterty.
• Nowoczesne routery używają do przechowywania informacji o routingu rodzaju drzewa o nazwie Próby.
• B-Trees i T-Trees są najczęściej używane przez popularne bazy danych do przechowywania swoich danych.
• Drzewo składni jest używane przez kompilatory do sprawdzania składni każdego napisanego programu.

Wniosek

Struktury danych zapewniają zorganizowany sposób przechowywania danych w celu łatwego zarządzania i efektywnej obsługi. Dla różnych typów danych istnieją różne typy struktur danych. Na podstawie rodzaju danych, które muszą być przechowywane, wybiera je użytkownik.

Drzewa to rodzaje takich struktur danych, w których można przechowywać hierarchiczny typ danych. Dane są przechowywane w węzłach, które czasami przechowują odniesienie do innych węzłów, zwanych węzłami potomnymi.

Na podstawie liczby węzłów podrzędnych drzewa można podzielić na różne typy, jak wspomniano w artykule. Na podstawie rozmieszczenia węzłów w typach drzewa, każda struktura drzewa ma skojarzone właściwości. Dzięki różnym typom operacji, które mogą być wykonywane przez różne klasy drzew, ten typ struktury danych znalazł zastosowanie w algorytmach sortowania i przechowywaniu danych.

Program Executive PG w rozwoju oprogramowania – specjalizacja w rozwoju pełnego stosu, kuratorowany przez upGrad i IIIT-Bangalore, może pomóc w poprawie twojego profilu i zapewnieniu lepszych możliwości zatrudnienia jako programista.