5 rodzajów drzewa binarnego wyjaśnione [z ilustracjami]

W informatyce różne struktury danych pomagają w porządkowaniu danych w różnych formach. Wśród nich drzewa są szeroko stosowanymi abstrakcyjnymi strukturami danych, które symulują hierarchiczną strukturę drzewa. Drzewo zwykle ma wartość główną i poddrzewa, które są tworzone przez węzły podrzędne z węzłów nadrzędnych. Drzewa to nieliniowe struktury danych.

Ogólna struktura danych w postaci drzewa nie ma ograniczeń co do liczby węzłów podrzędnych, które może przechowywać. Jednak tak nie jest w przypadku drzewa binarnego. W tym artykule dowiesz się o konkretnej strukturze danych drzewa – drzewie binarnym i typach drzewa binarnego .

Co to jest struktura danych drzewa binarnego?

Drzewo binarne to nieliniowa struktura danych typu drzewa z maksymalnie dwojgiem dzieci na każdego rodzica. Każdy węzeł w drzewie binarnym ma lewe i prawe odniesienie wraz z elementem danych. Węzeł na szczycie hierarchii drzewa nazywany jest węzłem głównym. Węzły zawierające inne podwęzły są węzłami nadrzędnymi.

Węzeł nadrzędny ma dwa węzły potomne: lewy i prawy potomek. Haszowanie, routing danych dla ruchu sieciowego, kompresja danych, przygotowywanie stert binarnych i binarne drzewa wyszukiwania to tylko niektóre z aplikacji korzystających z drzewa binarnego.

Terminologie związane z drzewami binarnymi i typami drzew binarnych

• Węzeł: reprezentuje punkt końcowy w drzewie.
• Korzeń: najwyższy węzeł drzewa.
• Rodzic: Każdy węzeł (oprócz korzenia) w drzewie, które ma co najmniej jeden własny węzeł podrzędny, nazywany jest węzłem nadrzędnym.
• Dziecko: Węzeł, który od razu pochodzi z węzła nadrzędnego, gdy odchodzi od korzenia, jest węzłem podrzędnym.
• Węzeł liścia: są to węzły zewnętrzne. Są to węzły, które nie mają dziecka.
• Węzeł wewnętrzny: Jak sama nazwa wskazuje, są to węzły wewnętrzne z co najmniej jednym dzieckiem.
• Głębokość drzewa: liczba krawędzi od węzła drzewa do korzenia.
• Wysokość drzewa: Jest to liczba krawędzi od węzła do najgłębszego liścia. Wysokość drzewa jest również uważana za wysokość korzenia.

Ponieważ jesteś już zaznajomiony z terminologią związaną z drzewem binarnym i typami drzew binarnych, nadszedł czas, aby zrozumieć składniki drzewa binarnego . Sprawdź nasze kursy nauki o danych, aby dowiedzieć się więcej o strukturze i komponentach binarnych.

Składniki drzewa binarnego

Istnieją trzy składniki drzewa binarnego . Z każdym węzłem drzewa binarnego powiązane są te trzy komponenty. Kluczową koncepcją dla programistów staje się zrozumienie tych trzech komponentów drzewa binarnego:

1. Element danych
2. Wskaźnik do lewego poddrzewa
3. Wskaźnik do prawego poddrzewa

Źródło

Te trzy składniki drzewa binarnego reprezentują węzeł. Dane znajdują się pośrodku. Lewy wskaźnik wskazuje węzeł potomny, tworząc lewe poddrzewo. Prawy wskaźnik wskazuje węzeł potomny po jego prawej stronie, tworząc prawe poddrzewo.

Przeczytaj: Najczęściej zadawane pytania i metody informacyjne w analizie danych

Rodzaje drzew binarnych

Istnieją różne typy drzew binarnych , a każdy z tych typów drzew binarnych ma unikalne cechy. Oto szczegóły każdego z typów drzew binarnych :

1. Pełne drzewo binarne

Jest to specjalny rodzaj drzewa binarnego, które ma albo zero dzieci, albo dwoje dzieci. Oznacza to, że wszystkie węzły w tym drzewie binarnym powinny mieć albo dwa węzły podrzędne swojego węzła nadrzędnego, albo węzeł nadrzędny jest sam węzłem liścia lub węzłem zewnętrznym.

Innymi słowy, pełne drzewo binarne jest unikalnym drzewem binarnym, w którym każdy węzeł z wyjątkiem węzła zewnętrznego ma dwoje dzieci. Kiedy przechowuje jedno dziecko, takie drzewo binarne nie będzie pełnym drzewem binarnym. Tutaj ilość węzłów liści jest równa liczbie węzłów wewnętrznych plus jeden. Równanie ma postać L=I+1, gdzie L to liczba węzłów liści, a I to liczba węzłów wewnętrznych.

Oto struktura pełnego drzewa binarnego:

2. Kompletne drzewo binarne

Kompletne drzewo binarne to inny specyficzny rodzaj drzewa binarnego, w którym wszystkie poziomy drzewa są całkowicie wypełnione węzłami, z wyjątkiem najniższego poziomu drzewa. Ponadto na ostatnim lub najniższym poziomie tego drzewa binarnego każdy węzeł powinien znajdować się po lewej stronie. Oto struktura kompletnego drzewa binarnego:

3. Idealne drzewo binarne

O drzewie binarnym mówi się, że jest „idealne”, jeśli wszystkie węzły wewnętrzne mają dokładnie dwoje dzieci, a każdy węzeł zewnętrzny lub liść znajduje się na tym samym poziomie lub tej samej głębokości w drzewie. Idealne drzewo binarne o wysokości „h” ma 2h – 1 węzeł. Oto struktura idealnego drzewa binarnego:

4. Zrównoważone drzewo binarne

O drzewie binarnym mówi się, że jest „zrównoważone”, jeśli wysokość drzewa wynosi O(logN), gdzie „N” to liczba węzłów. W zrównoważonym drzewie binarnym wysokość lewego i prawego poddrzewa każdego węzła powinna różnić się co najwyżej o jeden. Drzewo AVL i drzewo czerwono-czarne to kilka typowych przykładów struktury danych, które mogą generować zrównoważone drzewo wyszukiwania binarnego. Oto przykład zrównoważonego drzewa binarnego:

5. Zdegenerowane drzewo binarne

Mówi się, że drzewo binarne jest zdegenerowanym drzewem binarnym lub patologicznym drzewem binarnym, jeśli każdy węzeł wewnętrzny ma tylko jedno dziecko. Takie drzewa są podobne pod względem wydajności do połączonych list. Oto przykład zdegenerowanego drzewa binarnego:

Korzyści z drzewa binarnego

• Operacja wyszukiwania w drzewie binarnym jest szybsza w porównaniu z innymi drzewami
• Wystarczą tylko dwa przejścia, aby zapewnić elementy w posortowanej kolejności
• Łatwo jest zebrać elementy maksymalne i minimalne
• Przechodzenie po grafach wykorzystuje również drzewa binarne
• Konwersja różnych wyrażeń przyrostków i przedrostków jest możliwa przy użyciu drzew binarnych

Przeczytaj także: Drzewa decyzyjne w uczeniu maszynowym: funkcje, klasyfikacja, zalety i wady

Wniosek

Drzewo binarne jest jednym z najczęściej używanych drzew w strukturze danych. Każdy z typów drzew binarnych ma swoje unikalne cechy. Te struktury danych mają specyficzne wymagania w informatyce stosowanej. Mamy nadzieję, że ten artykuł o typach drzew binarnych był pomocny. upGrad oferuje różne kursy z zakresu nauki o danych, uczenia maszynowego, big data i nie tylko.

Jeśli jesteś zainteresowany nauką o danych, sprawdź program IIIT-B i upGrad Executive PG w dziedzinie Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1 -on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.