Struktury danych w JavaScripcie – Drzewo Binarne część 1

Drzewo binarne to kolejna struktura danych, którą przedstawię na blogu. Struktury drzew to bardzo rozległy temat w teorii nauk informatycznych. Drzewo binarne jest odmianą raczej prostą w zrozumieniu chociaż może wydawać się bardziej skomplikowane niż wcześniej przedstawiane przeze mnie struktury danych.

Dodatkową atrakcją w drzewach binarnych jest to, że do stworzenia JavaScriptowej implementacji mocno wykorzystam rekurencję. Warto ćwiczyć się w używaniu tej techniki ponieważ dobrze opanowana, daje ogromne możliwości.

Drzewo binarne to abstrakcyjna struktura danych, która składa się z przechowujących dane elementów zwanych węzłami lub liśćmi. Dlaczego abstrakcyjna? ponieważ tak naprawdę w żaden sposób nie jest podobna do drzewa, ale łatwo jest nam ją sobie wyobrazić jako strukturę przypominającą drzewo.

Każdy węzeł drzewa posiada jednego rodzica, który na niego wskazuje, oraz do dwóch, potomków, na które przechowuje wskaźniki. Wyjątkiem jest pierwszy węzeł znajdujący się na ‚szczycie’ drzewa zwany także korzeniem (root). Korzeń jest czymś jak head w liście.

Tak ‚wygląda’ przykładowe drzewo:

Koła reprezentują elementy drzewa a linie to łączenia pomiędzy nimi. Przykładowo, element B dostępny jest z elementu A. Po prawej stronie elementu A znajduje się element C. Element A to właśnie korzeń drzewa.

Tworząc drzewo można przyjąć pewną zasadę ‚układania’ elementów. Jest to ważne ponieważ, wpłynie na to jak będzie wyglądać dana implementacja. Jedną z najpopularniejszy praktyk jest ustawianie elementów mniejszych niż dany element po lewej stronie, a większych po prawej stronie. Takie drzewo nazywa się binarnym drzewem poszukiwań, inaczej BST (od angielskiego Binary Search Tree).

Tak może wyglądać przykładowa instancja drzewa BST:

Taka forma przechowywania danych może bardzo ułatwić życie programiście. Dzięki niej, łatwo jest dodawać, usuwać i odnajdywać elementy. Tego typu struktur są bardzo powszechne w informatyce!

Czas zabrać się za implementacje drzewa binarnego BST. W tym poście przedstawię bardzo prostą klasę, zawierającą jedynie podstawowe funkcje. Te funkcje, to dodawanie nowych elementów, oraz przechodzenie przez drzewo na trzy różne sposoby. Tak będzie wyglądał kod klasy:

Jak widać, pomimo prostej funkcjonalności, klasa BST zawiera sporo kodu. I tak dzięki rekurencji, oszczędzam sporo miejsca, ale o tym za chwilę.

Pierwszy element klasy BST, to definicja konstruktora, Node. Na jego podstawie tworzone będą elementy drzewa. Node, przyjmuje jeden argument, będzie to wartość przechowywana w danym elemencie, w polu key. Oprócz tego, każda instancja Node posiada dwa dodatkowe pola left oraz right. Jak łatwo się domyślić, będą to wskaźniki na kolejne elementy. Początkowo są one ustawione na null.

Kolejny element klasy BST to pole root. Wartość tego pola to wskaźnik na pierwszy element drzewa.

Dalsza część klasy to już tylko metody, operujące na danych. Tak jak w przypadku listy łączonej, nie ma tutaj jednego pola, przechowującego wszystkie dane. Elementy drzewa będą przedstawione przez instancje obiektu Node.

Pierwsza metoda to insert, służy ona do umieszczania nowych elementów w drzewie. Przyjmuje jeden argument: wartość, która będzie przechowywana przez nowy element. Wewnątrz metody, najpierw tworzę nową instancje Node. Następnie sprawdzam czy pole root jest puste, jeżeli tak, przypisuje do niego nowy element. W przeciwnym wypadku, wywołuję metodę insertHelper, która jako argumenty przyjmuje root obiektu, oraz nowy element.

insertHelper to pierwsza, dość prosta metoda, w której wykorzystuję rekurencję. Najpierw sprawdzam, czy aktualny element ma wartość większą niż nowy element. Jeżeli tak, sprawdzam, cze aktualny element wskazuje na coś wskaźnikiem left. Jeżeli tak, znów wywołuje metodę insertHelper, tym razem jako pierwszy argument, przekazuję to na co aktualny element pokazuje wskaźnikiem left. Drugi argument to wciąż nowy element.

Jeżeli natomiast wartość aktualnego elementu jest mniejsza lub równa od wartości nowego elementu, wykonuję tę samą operację ale teraz ‚na prawo’.

insertHelper będzie wywoływać się tak długo aż natrafi na pusty wskaźnik, do którego będzie mógł przypisać nowy element. Pomimo iż będą poukładane w konkretny sposób, dokładne położenia każdego elementu, zależy od kolejności dodawania. te same wartości, dodane w różnych kolejnościach, będą inaczej umiejscowione w drzewie.

Kolejna metoda obiektu BST to printNode. Ta bardzo prosta metoda służy do wypisania zawartości danego węzła w konsoli.

Następne trzy metody inOrder, preOrder oraz postOrder, służą do przejścia przez całe drzewo i wywołaniu na każdym z elementów jakiejś funkcji. Różnią się one tym, w jakiej kolejności przemieszczają się po elementach. Każda z tych metod ma odpowiednią metodę helper, która stosuje wywołania rekurencyjne.

Zdecydowanie najbardziej przydatną dla człowieka będzie zdecydowanie inOrder, ponieważ wypisuje ona elementy w kolejności od najmniejszego do największego. Nie przyjmuje ona żadnych argumentów i jedyne co robi to wywołuje inOrderHelper, który jako argumenty przyjmuje korzeń drzewa oraz metodę printNode.

I tu zaczyna robić się ciekawie. Metoda inOrderHelper, tak naprawdę ma bardzo prostą konstrukcję. Sprawdza ona czy przekazany jej element nie jest równy null. Jeżeli tak, nic się nie dzieje. Jeżeli nie, metoda wywołuje siebie samą na lewym wskaźniku aktualnego elementu. Następnie wywołuję funkcję przekazaną jej w argumencie i tej funkcji, przekazuje aktualny element. Na koniec, znów wywołuje samą siebie ale tym razem na prawym wskaźniku. Wywołania rekurencyjne jako drugi argument otrzymują oczywiście tę samą funkcję przekazaną na początku.

Zrozumienie tego jest kluczowe. Nie będę tutaj omawiał jak działa rekurencja, ale dam parę wskazówek, które mi pomogły pojąć jak to wszystko działa. Jednym ze sposobów na opanowanie tego, jest rozrysowanie strzałek na diagramie drzewa. Ich kierunek wskazuje kolejne wywołania funkcji zwrotnej. Wyglądałoby to w ten sposób:

Osobiście uważam, że nie jest to zbyt czytelne. Fakt wiadomo, na które elementy kiedy działa funkcja, ale nie do końca wiadomo dlaczego.

Przede wszystkim należy pamiętać, że JavaScript to język jednowątkowy. Oznacza to, że naraz działa tylko jeden proces. Jeżeli wewnątrz jednej funkcji uruchomiona zostanie inna funkcja. Zewnętrzna funkcja czeka, aż ta wewnętrzna zakończy swoją pracę i dopiero kontynuuje. Ja wywołane funkcje wyobrażam sobie jako bąbelki. Wykonana funkcja pęka i znika. Jeżeli funkcja znajduje się w funkcji, pękają od wewnątrz. Żaden bąbelek nie może pęknąć dopóki jakiś jeszcze się w nim znajduje. Oczywiście nie zawsze tak jest, ale w teorii się zgadza.

Każde rekurencyjne wywołanie funkcji inOrder tworzy nowy bąbelek w środku aktualnego. Nowy bąbelek tworzony jest zaraz po sprawdzeniu, czy aktualny element istnieje. Jeżeli tak, robię nowy bąbelek, tak dochodzę do najbardziej wysuniętego na lewo elementu. W końcu funkcja natrafia na element nie istniejący, bąbelek pęka. Teraz wykonywanie kontynuował będzie bąbelek, który jest najbliżej niego właśnie pękniętego, a zarazem najbardziej w środku innych bąbelków. Wywoła on funkcje zwrotną czyli wypisze wartość aktualnego elementu. Wiem, że będzie to najbardziej wysunięty na lewo element, a więc najmniejszy. Następnie wywołany zostanie bąbelek na prawo i cała historia się powtórzy w drugą stronę. Na najniższym poziomie drzewa, nic się nie wydarzy, ponieważ na prawo nic nie istnieje. Kolejny bąbelek pęka. wracamy do bąbelka wyżej. Kolejna jego akcja to wywołanie funkcji zwrotnej, następnie nowy bąbelek na prawo, tym razem coś już tam jest, większy niż poprzedni, ponieważ leży po prawej stronie… i tak dalej i tak dalej.

Mam nadzieję że ten dość chaotyczny opis pozwoli zrozumieć co tu się dzieję. Rekurencja to straszne draństwo i na początku trudno załapać o co chodzi. Nawet najprostsze przykłady wymagają konkretnego główkowania. Jednak jak już raz załapiesz o co chodzi, potem będzie z górki.

Rekurencja rekurencją, ale warto zwrócić uwagę w jaki sposób wywoływana jest metoda printNode. Ponieważ przekazuje ją jako argument funkcjom pomocniczym, jest wywoływana na każdym elemencie. Nic nie stoi na przeszkodzie, aby jako argument przekazać inną funkcję, która na przykład w jakiś sposób wpłynie na dane.

Kolejne metody: preOrder oraz postOrder, działają bardzo podobnie do inOrder. Różnią się jedynie kolejnością instrukcji wewnątrz funkcji rekurencyjnych. Nie będę ich opisywał ani rysował dla nich diagramów. Próba rozgryzienia tego na własną rękę to świetny sposób aby potrenować myślenie rekurencyjne.

Można sobie przy tym pomóc wywołując te funkcje i sprawdzając w jakiej kolejności podają wyniki. Aby stworzyć drzewo z obrazków powyżej, wystarczy ten kod:

A teraz wystarczy wyświetlić jego zawartość jedną z funkcji przechodzących przez drzewo:

To tyle jeśli chodzi o pierwszą część opisu klasy drzewa binarnego. W kolejnej części zaprezentuje sposoby na odnalezienie najmniejszego, lub największego elementu. A także jak wydajnie odnaleźć konkretny element. Do tego przedstawię metody usuwające pojedyncze elementy oraz całe gałęzie drzewa.

Jeżeli chcesz być na bieżąco z nowościami na blogu zachęcam do polubienia mojej strony na facebooku. Zawsze zamieszczam tam informacje o nowych wpisach.