Drzewo binarne w strukturze danych: właściwości, typy, reprezentacja i korzyści

Wśród różnych typów struktur danych znajdują się drzewa binarne, które mają więcej zastosowań niż większość innych typów. Ich najbardziej godne uwagi zastosowania obejmują programowanie peer-to-peer, wyszukiwanie, kryptografię, routery sieciowe o większej przepustowości niż inne oraz gry wideo 3D. Omówimy teraz szczegółowo, czym są drzewa binarne w nauce o danych, jakie są ich typy i jak są reprezentowane.

Czym są drzewa binarne?

Jeśli pracowałeś wcześniej nad normalnymi drzewami lub nawet znasz ich podstawy, wiedziałbyś, że nie ma ograniczeń, jeśli chodzi o liczbę dzieci, które różne węzły mogą mieć w tych drzewach. Drzewa binarne są pod tym względem nieco inne. Każdy rodzic lub węzeł w drzewach binarnych może mieć maksymalnie dwoje dzieci.

Wszystkie węzły w drzewie binarnym mają trzy podstawowe komponenty –

• element danych
• właściwe odniesienie
• lewe odniesienie

Węzeł znajdujący się na szczycie drzewa jest określany jako węzeł główny. Węzły nadrzędne to te, które mają dzieci. Węzły potomne i węzły nadrzędne są połączone ze sobą poprzez odniesienia. Węzły, które nie mają żadnych dzieci, są określane jako węzły liści.

Jest oczywiste, że węzły w drzewach binarnych mogą mieć jedno dziecko, dwoje dzieci lub w ogóle nie mieć dzieci. Drzewa binarne nie są liniowymi strukturami danych, takimi jak kolejki, tablice, stosy i połączone listy. Zamiast tego są to hierarchiczne struktury danych.

Sprawdź: Pomysły na projekty Data Science dla początkujących

Ważne właściwości węzłów w drzewach binarnych

Lepsze zrozumienie tych właściwości pomoże ci w pełni wykorzystać tę dyskusję na temat drzew binarnych. Głębokość różnych węzłów jest definiowana jako liczba węzłów istniejących na drodze łączącej root z konkretnym węzłem. Dlatego głębokość węzła głównego wynosi 0. Z drugiej strony wysokość różnych węzłów w drzewie binarnym to liczba węzłów leżących na ścieżce łączącej dany węzeł z węzłem głównym. Dlatego wysokość węzłów liści wynosi 0.

Jak wyraźnie widać, głębokość węzła mierzy się zaczynając od węzła głównego, a następnie schodząc w dół, aby dotrzeć do tego węzła. Z drugiej strony, jeśli chodzi o obliczanie wysokości, zaczynamy w danym węźle, a następnie kierujemy się w stronę węzła głównego. W obu przypadkach zaczynamy od 0. Są ludzie, którzy również mierzą wysokość i głębokość od 1, a nie od 0, co nie jest złe i jest to, co wolą różni ludzie.

Teraz maksymalna głębokość węzła jest zdefiniowana jako głębokość drzewa binarnego. Podobnie maksymalna wysokość węzła jest definiowana jako wysokość drzewa binarnego. Tak więc wysokość i głębokość drzewa binarnego są zawsze takie same.

Dowiedz się więcej: Struktury danych i algorytm w Pythonie

Co to jest drzewo wyszukiwania binarnego?

Drzewo wyszukiwania binarnego jest najczęstszym ze wszystkich innych typów drzew binarnych. Jest to wyspecjalizowane drzewo binarne, które zawiera właściwości, które są inne i bardziej przydatne niż jakakolwiek inna forma drzewa binarnego. Czym dokładnie jest drzewo wyszukiwania binarnego lub BST? Tak jak sugeruje jego nazwa, drzewo wyszukiwania binarnego służy do wyszukiwania danych w drzewie.

BST ma właściwości, które ułatwiają wydajne wyszukiwanie. BST to drzewo binarne, w którym klucz węzła jest mniejszy i większy niż odpowiednio węzły w prawym poddrzewie i węzły w lewym poddrzewie.

Reprezentacja drzew binarnych

1. Reprezentacja połączona

Drzewa binarne w reprezentacji połączonej są przechowywane w pamięci jako listy połączone. Listy te zawierają węzły, które nie są przechowywane w sąsiednich lub sąsiednich lokalizacjach pamięci i są połączone ze sobą poprzez relację rodzic-dziecko skojarzoną z drzewami.

W tej reprezentacji każdy węzeł ma trzy różne części –

• wskaźnik wskazujący na prawy węzeł,
• wskaźnik wskazujący na lewy węzeł,
• element danych.

To jest bardziej powszechna reprezentacja. Wszystkie drzewa binarne składają się ze wskaźnika korzenia, który wskazuje kierunek węzła korzenia. Kiedy widzisz węzeł główny wskazujący na null lub 0, powinieneś wiedzieć, że masz do czynienia z pustym drzewem binarnym. Prawy i lewy wskaźnik przechowują adres prawego i lewego dziecka drzewa.

2. Reprezentacja sekwencyjna

Chociaż jest prostsza niż reprezentacja połączona, jej nieefektywność sprawia, że ​​jest mniej preferowaną reprezentacją drzewa binarnego tych dwóch. Nieefektywność polega na ilości miejsca potrzebnego do przechowywania różnych elementów drzewa. Reprezentacja sekwencyjna wykorzystuje tablicę do przechowywania elementów drzewa.

Liczba węzłów drzewa binarnego określa rozmiar używanej tablicy. Węzeł główny drzewa binarnego znajduje się w pierwszym indeksie tablicy. Indeks, pod którym przechowywany jest konkretny węzeł, określi indeksy, w których będą przechowywane prawe i lewe dzieci węzła. Puste drzewo ma wartość null lub 0 jako pierwszy indeks.

Rodzaje drzew binarnych

1. Pełne drzewa binarne: pełne drzewa binarne to te drzewa binarne, których węzły mają dwoje dzieci lub nie mają ich wcale. Innymi słowy, drzewo binarne staje się pełnym drzewem binarnym, gdy oprócz liści wszystkie jego węzły mają dwoje dzieci.
2. Kompletne drzewa binarne: Kompletne drzewa binarne to takie, których wszystkie poziomy są całkowicie wypełnione. Jedynym wyjątkiem może być ich ostatni poziom, którego klawisze znajdują się głównie po lewej stronie. Sterta binarna jest często traktowana jako przykład pełnego drzewa binarnego.
3. Doskonałe drzewa binarne: Doskonałe drzewa binarne to drzewa binarne, których liście są na tym samym poziomie i których węzły wewnętrzne mają dwoje dzieci. Typowym przykładem doskonałego drzewa binarnego jest drzewo genealogiczne przodków.
4. Patologiczne zdegenerowane drzewa binarne: Zdegenerowane drzewa to te drzewa binarne, których węzły wewnętrzne mają jedno dziecko. Ich poziomy wydajności są podobne do list połączonych. Dowiedz się więcej o rodzajach drzewa binarnego.

Przeczytaj: Sześć najczęściej używanych struktur danych w R

Zalety drzew binarnych

1. Idealny sposób na hierarchiczny sposób przechowywania danych
2. Odzwierciedlaj relacje strukturalne istniejące w danym zbiorze danych
3. Szybsze wstawianie i usuwanie niż połączone listy i tablice
4. Elastyczny sposób przechowywania i przenoszenia danych
5. Służą do przechowywania jak największej liczby węzłów
6. Są szybsze niż listy połączone i wolniejsze niż tablice, jeśli chodzi o dostęp do elementów

Wniosek

W tym blogu omówiliśmy, czym są drzewa binarne w strukturach danych, a także omówiliśmy ich typy, ich reprezentacje i korzyści. Dwa główne zastosowania drzew to wyszukiwanie i przechowywanie danych, a zatem są one integralną częścią nauki o danych i powiązanych z nią dziedzinach.

Jeśli jesteś ciekawy, aby dowiedzieć się o drzewach binarnych w strukturach danych, nauce o danych, sprawdź program Executive PG w dziedzinie Data Science IIIT-B i upGrad, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty, mentoring z ekspertami z branży, 1 na 1 z mentorami branżowymi, ponad 400 godzin nauki i pomoc w pracy z najlepszymi firmami.