Wyjaśnienie 5 typów drzew binarnych w strukturze danych

Drzewo binarne to nieliniowa drzewiasta struktura danych, która zawiera każdy węzeł z maksymalnie 2 elementami potomnymi. Nazwa binarna sugeruje liczbę 2, więc każde drzewo binarne może mieć lewe i prawe dziecko.

Wskaźnik przedstawia drzewo binarne do najwyższego węzła, zwykle zwanego korzeniem drzewa. Każdy węzeł w drzewie binarnym zawiera dane, wskaźnik do lewego dziecka i wskaźnik do prawego dziecka. Wskaźniki służą do implementacji drzewa binarnego. Wskaźnik korzenia oznacza pierwszy węzeł w drzewie. Aby utworzyć drzewo binarne, musisz najpierw utworzyć węzeł.

Po zapoznaniu się ztym, czym jest drzewo binarne w strukturze danych , należy również poznać podstawowe operacje wykonywane na drzewie binarnym.Możesz wykonywać funkcje, takie jak wstawianie elementu, usuwanie elementu, wyszukiwanie elementu i przechodzenie przez drzewo binarne.

Każdedrzewo binarne w strukturze danych jest używane na dwa różne sposoby w informatyce.Po pierwsze, służą do uzyskiwania dostępu do węzłów w zależności od określonych etykiet lub wartości powiązanych z każdym węzłem. Po drugie, są używane jako reprezentacje danych o odpowiedniej strukturze rozgałęzionej.

Zanim przejdziemy przez różnetypy drzew binarnych , najpierw zapoznajmy się z terminologią używaną w drzewie binarnym.

Węzeł: przechowuje wartość danych w drzewie binarnym.

Korzeń: Najwyższy węzeł w dowolnym drzewie binarnym nazywany jest korzeniem drzewa.

Rozmiar: określa liczbę węzłów w drzewie binarnym.

Węzeł nadrzędny: węzeł w drzewie binarnym z dzieckiem.

Węzeł potomny: Jest to węzeł, który pochodzi z węzła nadrzędnego oddalającego się od korzenia drzewa binarnego.

Węzeł wewnętrzny: Jest to węzeł z co najmniej jednym dzieckiem w drzewie binarnym.

Węzeł liścia: Jest to węzeł bez dziecka.Jest to alternatywnie węzeł zewnętrzny.

Głębokość drzewa węzłów: jest obliczana w kontekście konkretnego węzła.Nazywa się to liczbą krawędzi od określonego węzła do korzenia.

Wewnętrzna długość ścieżki drzewa: odnosi się do sumy poziomów każdego wewnętrznego węzła w drzewie binarnym.

Długość ścieżki zewnętrznej drzewa: Jest definiowana jako suma poziomów każdego zewnętrznego węzła w drzewie binarnym.

Wysokość węzła w drzewie: Jest to liczba krawędzi od określonego węzła do najgłębszego węzła liścia drzewa binarnego.Wysokość korzenia zawsze będzie większa niż wysokość innych węzłów w drzewie binarnym.

Przyjrzyjmy się teraz szczegółom 5typów drzew binarnych.

Rodzaje drzew binarnych

1. Pełne drzewo binarne

Todrzewo binarne w strukturze danych jest również znane pod nazwami - Właściwe drzewo binarne i Ścisłe drzewo binarne.Jest to jeden z najbardziej podstawowychtypów drzew binarnych w strukturze danych.Pełne drzewo binarne jest zdefiniowane jako drzewo binarne, w którym każdy węzeł powinien mieć dwoje dzieci lub nie mieć ich wcale.

Jest alternatywnie scharakteryzowane jako drzewo binarne, w którym każdy węzeł zawiera dwoje dzieci z wyjątkiem węzłów liścia. Węzły, w których przechowywany jest adres węzła głównego, nazywane są węzłami potomnymi korzenia. Te węzły pozbawione dzieci nazywane są węzłami liści.

Musisz przejść wszystkie węzły, aby sprawdzić, czy drzewo jest drzewem binarnym. Kod zwróci „False”, jeśli jakikolwiek węzeł ma jedno dziecko. Zwróci „True”, jeśli wszystkie węzły mają 0 lub 2 dzieci.

Oto właściwości pełnego drzewa binarnego:

• Liczba węzłów liści jest równa liczbie węzłów wewnętrznych + 1. Na przykład, jeśli liczba węzłów wewnętrznych wynosi 4, liczba węzłów liści wynosi 5.
• Maksymalna liczba węzłów i liczba węzłów w drzewie binarnym są sobie równe. Jest reprezentowany jako 2h+1-1.
• Minimalna liczba węzłów w pełnym drzewie binarnym to 2h-1.
• Minimalna wysokość pełnego drzewa binarnego to log 2 (n+1) – 1.
• Maksymalna wysokość pełnego drzewa binarnego to h = (n+1)/2.

2. Doskonałe drzewo binarne

Idealne drzewo binarne jest jednym z tychtypów drzew binarnych , w których każdy węzeł musi mieć 0 lub 2 dzieci, a poziom każdego węzła liścia musi być taki sam.Innymi słowy, doskonałedrzewa binarne w strukturze danych definiuje się jako takie drzewa, w których wszystkie węzły wewnętrzne mają dwie gałęzie, a węzły bez gałęzi (węzły liścia) znajdują się na tym samym poziomie.

W tym kontekście poziom węzła to odległość lub wysokość od węzła głównego. Doskonałe drzewo binarne można uznać za kompletne drzewo binarne, w którym ostatni poziom jest również całkowicie zajęty.

Ucz sięonlinena kursach nauki o danychna najlepszych światowych uniwersytetach. Zdobądź programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

3. Ukończ drzewo binarne

Kompletne drzewo binarne jest jednym z tych typów drzew binarnych w strukturze danych , w którym wszystkie poziomy drzewa są w pełni wypełnione.Ostatni poziom drzewa binarnego może być całkowicie wypełniony lub nie. Jednak każdy węzeł musi znajdować się w skrajnej lewej pozycji na ostatnim poziomie węzła. Węzły muszą być uwzględnione od lewej strony.

Są jednym z podstawowychtypów drzew binarnych , ponieważ oferują najlepszy stosunek liczby węzłów do wysokości drzewa.

Oto kluczowe właściwości kompletnego drzewa binarnego:

• Maksymalna liczba węzłów to 2 h+1 – 1.
• Minimalna liczba węzłów to 2 h .
• Minimalna wysokość to log 2 (n+1) – 1.

4. Zrównoważone drzewo binarne

W zrównoważonych drzewach binarnych wysokość drzewa to log 2 całkowitej liczby węzłów. Załóżmy, że wysokość drzewa wynosi h, a całkowita liczba węzłów wynosi n. Równanie do obliczenia wysokości to h = log(n). Maksymalna różnica wysokości między prawym poddrzewem a lewym poddrzewem musi wynosić „1”.

Różnica może mieć inne wartości, takie jak 0 i -1. Te typy drzew binarnych są również nazywane drzewami AVL.Jednym z dobrze znanych przykładów zrównoważonych drzew binarnych jest drzewo czerwono-czarne.

Możesz zaimplementować następujący kod, aby uruchomić zrównoważone drzewo binarne.

Węzeł klasy prywatnej {

prywatna wartość całkowita;

pozostawiono węzeł prywatny;

prawo do węzła prywatnego;

}

public boolean isBalanced(węzeł n) {

if (zbalansowana wysokość drzewa(n) > -1)

zwróć prawdę;

zwróć fałsz;

}

public int balancedrzewoWysokość(węzeł n) {

jeśli (n == zero)

zwróć 0;

int h1 = zbalansowana wysokość drzewa (n. prawa);

int h2 = zbalansowanaWysokość(n.lewo);

jeśli (h1 == -1 || h2 == -1)

powrót -1;

jeśli (Math.abs(h1 – h2) > 1)

powrót -1;

jeśli (h1 > h2)

zwróć h1 + 1;

zwróć h2 + 1;

}

Sprawdź nasze amerykańskie programy nauki o danych

5. Zdegenerowane drzewo binarne

Zdegenerowane drzewo binarne jest jednym z rzadziej używanychtypów drzewa wyszukiwania binarnego .Jest to drzewo binarne, w którym każdy węzeł ma tylko jedno dziecko, tj. lewe lub prawe dziecko. Żaden węzeł nie powinien mieć zarówno lewych, jak i prawych dzieci.

Przeczytaj nasze popularne artykuły w USA — Data Science

Wniosek

Niezbędne jest zrozumienie,czym jest drzewo binarne w strukturze danych , jeśli chcesz go używać do różnych aplikacji.Implementacja różnych funkcji na drzewach binarnych może pomóc w efektywnym organizowaniu i przechowywaniu danych.

Studiowanie wielu typów drzew binarnych pomaga efektywniej wykonywać operacje w złożoności czasowej. Podstawy nauki o danych, w tymbinarna struktura danych, ułatwiają rozpoczęcie nauki o danych.Następnie możesz pracować nad zaawansowanymi projektami data science, aby poprawić swoje umiejętności i portfolio.

Rozpocznij swoją przygodę z uczeniem maszynowym na upGrad

Jeśli chcesz nauczyć się Data Science, możesz kontynuować program Master of Science in Data Science upGrad . Ten 24-miesięczny kurs zapewnia umiejętności takie jak Python, wdrażanie modeli uczenia maszynowego, przetwarzanie BD przy użyciu platformy Spark, analizy predykcyjne i statystyki oraz nadzorowane i nienadzorowane modele uczenia maszynowego. Kurs jest odpowiedni dla ambitnych menedżerów, absolwentów MBA, inżynierów i profesjonalistów z różnych dziedzin.

Ukończenie tego kursu pomoże Ci pracować jako Data Engineer, Big Data Analyst, Machine Learning Engineer i Data Scientist.