Dawno się nie widzieliśmy! Właśnie z tego powodu przygotowałem dla Was kolejny wpis. Tym razem, nie podejmiemy się jednak tematu algorytmów sortowania, a kontynuować będziemy serię dotyczącą struktur danych. Zanim rozpoczniecie czytanie poniższego wpisu, zachęcam was do zapoznania się z poprzednimi częściami tej serii. Znajdziecie w nich opis stosu, listy jednokierunkowej oraz dwukierunkowej. W tych wpisach poznacie zagadnienia powiązane z podstawami struktur danych, które warto znać jako przyszły programista. Przejdźmy jednak do właściwej części tekstu, w której odpowiemy sobie na najważniejsze pytanie.

Czym jest drzewo?

Drzewo jako struktura danych, to grupa węzłów połączonych krawędziami. Węzeł początkowy, nazywany jest powszechnie korzeniem (root), a wierzchołki z których nie wychodzą żadne krawędzie, liśćmi (leafs). Każdy węzeł połączony z węzłem wyżej jest jego dzieckiem.

Jeżeli w drzewie każdy z węzłów ma maksymalnie dwoje dzieci, jest to drzewo binarne. W tym tekście omówimy sobie dokładniej BST (binary search tree) – podstawowy rodzaj drzewa binarnego.

BST, czyli binarne drzewo poszukiwań posiada jedną cechę charakterystyczną – po lewej stronie każdego poddrzewa znajdują się elementy mniejsze od wartości korzenia tego poddrzewa, a po prawej większe bądź równe. Może wydawać się to dość skomplikowane, lecz łatwo zrozumieć zasadę jego działania dzięki przykładowi.

BST – zasada działania

Weźmy drzewo, które posiada na początku tylko jeden węzeł (korzeń) o wartości 12. Chcąc dodać do tego drzewa nowy węzeł o wartości 5, przyrównujemy wartość nowego węzła do węzła początkowego. Jeśli będzie większa bądź równa idziemy na prawo, w przeciwnym wypadku idziemy na lewo. 5 jest mniejsze od 12, a co za tym idzie poruszamy się na lewo. Ze względu na to, że korzeń nie ma żadnych dzieci, lewa strona jest pusta. Oznacza to, że możemy wstawić w tym miejscu węzeł. Następnie wstawmy węzeł o wartości 33. Analogicznie poruszamy się w prawo, gdzie znajdziemy wolne miejsce na węzeł. Co należy jednak zrobić, gdy zechcemy w tym momencie wstawić do drzewa węzeł o wartości 7?

W pierwszym kroku przyrównujemy wartość nowego węzła do wartości korzenia. Ze względu na to, że wartość 7 jest mniejsza od 12, przechodzimy w lewo. Następnie przyrównujemy wartość 7 do wartości lewego dziecka korzenia, czyli 5. Wartość tego węzła jest mniejsza od wartości nowego, tak więc przechodzimy w prawo. Tam nie znajdziemy żadnego węzła, więc możemy wstawić w tym miejscu węzeł o wartości 7. Poniższa animacja pomoże wam zobrazować sobie ten przykład.

Podsumowując – gdy chcemy dodać jakikolwiek nowy węzeł staramy się znaleźć wolne miejsce, przechodząc w prawo, jeśli wartość nowego węzła jest większa bądź równa od aktualnie wskazywanego, lub w lewo, gdy jest mniejsza.

Drzewo BST – implementacja w C++

Nim zaprezentuję wam kod, należy poruszyć ważną kwestię. Według zasad drzewa BST, każdy z węzłów musi przechowywać przynajmniej: zmienną wartości węzła, wskaźnik na rodzica, wskaźnik na lewe dziecko i wskaźnik na prawe dziecko. Jeśli dany węzeł nie ma dziecka, po danej stronie, wskaźnik należy ustawić na wartość NULL. Dzięki temu, jesteśmy w stanie zweryfikować w prosty sposób czy dany wskaźnik wskazuje na dziecko, czy na pustą przestrzeń.

Poniższa implementacja posiada funkcje pozwalające na dodanie węzła, usunięcie węzła oraz znalezienie maksymalnej i minimalnej wartości w drzewie.

Podsumowanie

Drzewa (a zwłaszcza te binarne) to niezwykle popularny rodzaj struktury danych w informatyce. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Warto więc znać zasadę ich działania. Jeśli jesteście głodni wiedzy, mogę wam zdradzić, iż niedługo pojawi się kolejny wpis dotyczący struktur danych. Do zobaczenia 😉

You Might Also Like
Dodaj komentarz

Odwiedź Binarnie.pl na FB

Cześć, jeżeli publikowane treści okażą się dla Ciebie pomocne to zapraszam Cię do polubienia Binarnie.pl na Facebook'u 👍 Bądź pewien, że nic nowego Cię nie ominie 👨🏻‍💻


This will close in 20 seconds