Przewodnik dla początkujących po drzewach binarnych

Jeśli ukończyłeś kurs na temat struktur danych na wydziale informatyki lub jesteś programistą samoukiem, prawdopodobnie natrafiłeś na termin „drzewa binarne”. Chociaż mogą brzmieć nieco przytłaczająco i skomplikowanie, koncepcja drzewa binarnego jest dość prosta.

Czytaj dalej, gdy analizujemy drzewa binarne i dlaczego są one niezbędną podstawową koncepcją dla programistów.

Czym są drzewa binarne?

Drzewa binarne są jednymi z pierwszych struktur danych, których studenci uczą się na kursie dotyczącym struktur danych. Drzewo binarne składa się z wielu węzłów, a każdy węzeł drzewa binarnego zawiera dwa wskaźniki, które wskazują lewy i prawy podrzędny węzły danych.

Pierwszy węzeł w drzewie binarnym nazywa się „root”. Węzły ostatniego poziomu drzewa nazywane są liśćmi.

Każdy węzeł zawiera element danych i dwa wskaźniki węzła. Puste drzewo binarne jest reprezentowane przez pusty wskaźnik. Jak już zapewne się zorientowałeś, drzewa binarne mogą mieć tylko dwoje dzieci (stąd nazwa).

Rodzaje binarnych struktur drzewiastych

Istnieje kilka różnych binarnych struktur drzewiastych w zależności od sposobu rozmieszczenia węzłów. Drzewo binarne nazywane jest pełnym drzewem binarnym, gdy każdy węzeł w drzewie ma zero lub dwoje dzieci. W idealnym drzewie binarnym wszystkie węzły mają dwoje dzieci, a wszystkie liście znajdują się na tej samej głębokości.

Związane z: Najlepsze sposoby na naukę kodowania za darmo

Kompletne drzewo binarne ma węzły wypełnione na każdym poziomie, z wyjątkiem ostatniego poziomu. W kompletnych drzewach binarnych węzły są skoncentrowane po lewej stronie korzenia. Inną powszechną strukturą jest zrównoważone drzewo binarne; w tej strukturze wysokości prawego i lewego poddrzewa muszą różnić się najwyżej o jeden. Wymagane jest również zrównoważenie lewego i prawego poddrzewa.

Należy zauważyć, że wysokość zrównoważonego drzewa binarnego to O(logn), gdzie n jest liczbą węzłów w drzewie.

W niektórych przypadkach, jeśli każdy węzeł ma tylko jedno lewe lub prawe dziecko, drzewo binarne może stać się skrzywionym drzewem binarnym. Będzie wtedy zachowywać się jak lista połączona, takie drzewa są również nazywane drzewem zdegenerowanym.

Co to są drzewa wyszukiwania binarnego?

Drzewo wyszukiwania binarnego (BST) jest zasadniczo uporządkowanym drzewem binarnym ze specjalną właściwością znaną jako właściwość „drzewa wyszukiwania binarnego”. Właściwość BST oznacza, że ​​węzły o wartości klucza mniejszej niż korzeń są umieszczane w lewym poddrzewie, a węzły o wartości klucza większej niż korzeń są częścią prawego poddrzewa.

Właściwość BST musi być true dla każdego kolejnego węzła nadrzędnego w drzewie.

Drzewa wyszukiwania binarnego umożliwiają szybkie wstawianie i wyszukiwanie. Operacje wstawiania, usuwania i wyszukiwania mają najgorszą złożoność czasową O(n), która jest podobna do połączonej listy.

Korzyści z drzew binarnych

Drzewa binarne oferują wiele korzyści, dlatego pozostają bardzo przydatną strukturą danych. Mogą służyć do pokazywania strukturalnych relacji i hierarchii w zestawie danych. Co ważniejsze, drzewa binarne umożliwiają wydajne wyszukiwanie, usuwanie i wstawianie.

Zaimplementowanie i utrzymanie drzewa binarnego jest również bardzo łatwe. Drzewo binarne oferuje programistom korzyści wynikające z uporządkowanej tablicy i połączonej listy; wyszukiwanie w drzewie binarnym jest tak szybkie, jak w posortowanej tablicy, a operacje wstawiania lub usuwania są tak samo wydajne, jak w przypadku list połączonych.

Drzewa binarne są ważnymi strukturami danych

Drzewa binarne są bardzo ważną strukturą danych i ważne jest, aby programiści mogli swobodnie stosować je w swoich programach. Często ankieterzy zadają proste problemy z drzewami binarnymi, takie jak przechodzenie, maksymalna głębokość, dublowanie itp.

Zdecydowanie zalecamy zrozumienie koncepcji drzewa binarnego i zapoznanie się z typowymi problemami podczas rozmowy kwalifikacyjnej.

TreeViz: prosty sposób na wizualizację struktur danych

Czytaj dalej

O autorze