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

Czas na dalszy ciąg JavaScriptowej implementacji drzewa binarnego. Ostatnim razem pokazałem jak do drzewa dodawać elementy i jak się po nim przemieszczać.

W tym poście przedstawię techniki przeszukiwania drzewa, oraz usuwania elementów.

JavaScript noob Drzewo Binarne

W moimi drzewie da się już dodawać elementy i wyświetlać je w odpowiedniej kolejności. Jednak struktura z takimi funkcjami nie na wiele się przyda. Dlatego dodam do niej możliwość przeszukiwania. Drzewo świetnie nadaję się do przechowywania danych, które będziemy często przeszukiwać. A to dlatego, że tę operację jest bardzo łatwo wykonać i działa ona bardzo szybko.

Aby zrozumieć dlaczego tak jest, najpierw spróbuję odnaleźć najwyższą i najniższą wartość znajdującą się w tym drzewie:

drzewBST

Od razu widać, gdzie znajdują się interesujące mnie wartości. Najniższa wartość na drzewie zawsze jest elementem wysuniętym najbardziej na lewo. Najwyższa za to, znajduje się najbardziej po prawej stronie. Napisanie funkcji, która je znajduje, będzie bardzo proste. Oto metody, które dodam do mojej implementacji:

Tym razem nie kombinowałem z rekurencją. W przypadku tak prostolinijnej logiki byłoby to zbędne.

Na początku metody szukającej najniższej wartość, findMin, sprawdzam czy w drzewie istnieje korzeń, jeżeli nie, od razu zwracam null. W przeciwnym razie przypisuję korzeń do tymczasowej zmiennej node. Następnie uruchamiam pętle while, która działa dopóki zmienna node posiada wartość na wskaźniku left. Z każdym obiegiem zmieniam node tak aby wskazywał na swoje lewo. Kiedy nie ma już na co wskazywać, pętla staje i metoda zwraca klucz aktualnego elementu.

Metoda findMax działa prawie identycznie, tylko zamiast na lewo, wskazuję na prawo. Proste 🙂

Kolejna metoda, wyszukuje konkretne wartości:

Tutaj już korzystam z rekurencji, więc tworzę sobie metodę pomocniczą. W metodzie ‚interfejsowej’ search przyjmowany jest jeden argument, poszukiwany klucz. Następnie wywoływana jest metoda searchHelper, której przekazywany jest korzeń drzewa, oraz przekazany wcześniej klucz.

Metoda searchHelper, przyjmuje dwa argumenty, element drzewa oraz szukany klucz.

Jeżeli klucz elementu równy jest null, metoda zwraca false. Jeżeli jest mniejszy, metoda zwraca samą siebie, ale jako pierwszy argument przekazuje wskaźnik na lewo. W przypadku gdy klucz jest większy, metoda zwraca samą siebie, ale pierwszy argument to wskaźnik na prawo. Jeśli żadne z powyższych nie są prawdziwie, oznacza to, że klucz aktualnego elementu jest równy szukanemu. To oznacza, że metoda odnalazła szukany element i zwracane jest true.

Jak widać przeszukiwanie drzew binarnych jest bardzo proste a zarazem bardzo efektywne. Pozostało już tylko dodanie funkcjonalności usuwania elementów drzewa.

Oto kod odpowiednich metod:

Tutaj zdecydowanie dzieje się najwięcej. Nie jest to prosty mechanizm, ale nie jest też jakoś diabelnie skomplikowany. Postaram się wytłumaczyć go w miarę klarownie, jednak uważam, że najlepiej, dojść do tego samemu studiując kod.

Metoda remove, wywołuje metodę removeHelper. Wynik działania removeHelper przypisywany jest do korzenia drzewa. Dlaczego tak? Ponieważ funkcja removeHelper zwraca nowe drzew, które nie zawiera usuwanego elementu. Robi to w sumie rekurencyjnie, po kawałeczku, ale to pierwsze wywołanie zwraca całe drzewo 🙂 .

Oczywiście, jeżeli przekazany do removeHelper element jest równy null, funkcja zwraca null. Jeżeli tak nie jest to następne zadanie to odnalezienie elementu który ma być usunięty. To już pokazywałem, porównuję element z aktualnym i poruszam się w odpowiednią stronę.

Ciekawie robi się w momencie kiedy docieram do szukanego elementu. Od tego miejsca są tak naprawdę trzy scenariusze. Każdy z nich reprezentowany przez kolejne wyrażenie if w kodzie.

Pierwszy scenariusz jest taki, że szukany element nie posiada żadnego elementu pochodnego. Jest to prosta sytuacja. Element ustawiany jest na null i zwracany (a potem znów zwracany i znów i znów 😛 aż dojdzie do korzenia wersja).

Druga sytuacja polega na tym, że element ma jeden element pochodny. Ta sytuacja też nie jest skomplikowana 🙂 Musze ustalić po której stronie jest element pochodny. Gdy już to wiem, przypisuje jego wartość do aktualnego elementu. Podobnie jak w liście jednokierunkowej, Element dalszy zastępuje ten bliższy.

Trzeci możliwy scenariusz, jest taki, że element który mam usunąć posiada dwa elementy pochodne. Najpierw muszę znaleźć najwyższy element niższy od usuwanego. Wiem, że będzie to najniższy element w ‚pod-drzewie’ po prawej stronie (jak ktoś nie wierzy, proszę zobaczyć na rysunki 🙂 ). Odnajduję ten element przy pomocy prościutkiej metody pomocniczej findSmallestFrom. Standardowa findMin, się tu nie sprawdzi, ponieważ przeszukuje ona całe drzewo.

Wartość odnalezionego element przypisuję do aktualnego. Na koniec pozostało mi tylko usunięcie zbędnego już elementu po prawej stronie. Robię ponownie wywołując removeHelper. Wynik oczywiście przypisuję do prawego wskaźnika aktualnego elementu.

Nie jest to łatwe do pojęcia od razu, ale nie jest to też aż tak trudne do opanowania. Na pewno może wymagać trochę czas. Rozrysowanie sobie wszystkich trzech sytuacji na pewno pomoże. Osobiście uważam, że w strukturach danych, które tu opiszę, usuwanie elementów z drzewa BST jest najbardziej skomplikowaną operacją, a i tak nie jest bardzo trudno. Warto wiedzieć jak to działa 🙂

To tyle na dziś, a już niedługo ostatnia struktura danych, którą przedstawię na blogu – graf. Jeżeli nie chcesz tego przegapić zachęcam do polubienia mojej strony na facebooku. Zawsze zamieszczam tam informacje o nowych wpisach.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *