Binarne Drzewo Poszukiwań (BST)

Wstęp

Binarne Drzewo Poszukiwań jest dynamiczną strukturą danych, która pozwala przechowywać dane w określonej hierarchii. Jest ono wykorzystywane wszędzie tam gdzie jest potrzebne względnie szybkie wyszukiwanie elementów. Można je również wykorzystać w celu szybkiego posortowania danych.

Opis

Drzewo Binarne, aby stało się Binarnym Drzewem Poszukiwań musi spełniać warunek, że każdy węzeł ma maksymalnie dwóch potomków. Lewy potomek musi mieć mniejszą wartość niż rodzic, a prawy musi mieć większą wartość niż rodzic. Początkowo drzewo składa się jedynie z pustego korzenia, który jest węzłem wejściowym drzewa.

W celu dodania elementu do Drzewa Binarnego należy ustalić jego pozycję. Poszukiwania zaczynamy od węzła początkowego (korzenia). Jeśli dany węzeł nie ma przypisanej wartości to ją przypisujemy. W przeciwnym wypadku należy porównać dodawaną wartość z wartością w węźle. Jeśli jest mniejsza to poszukiwania kontynuujemy dla lewego potomka, a jeśli jest większa to dla prawego.

Przykład

Poniższa sseria rysunków przedstawia proces dołączania kolejnych elementów do drzewa z listy L := {6, 4, 5, 8, 3}. Pierwszy element można dołączyć bez większych problemów. Następne wymagają wykonania odpowiedniej ilości porównaj zanim zostanie znalezione ich miejsce.

Krok 1: Dołączanie elementu 6

Krok 2: Dołączanie elementu 4

Krok 3: Dołączanie elementu 5

Krok 4: Dołączanie elementu 8

Krok 5: Dołączanie elementu 3

Implementacja

Węzeł

Węzeł to pojemnik, który ma przechowywać określoną wartość, ale też wiedzieć, który element znajduje się po jego lewej oraz prawej stronie. Oczywiście jeśli kolejne elementy istnieją. Deklaracja klasy Wezel może przedstawiać się następująco:

1. template <class T>
2. class Wezel {
3. public:
4.   Wezel<T>* lewy = NULL;
5.   Wezel<T>* prawy = NULL;
6.   T wartosc = NULL;
8.   Wezel(T a) {
9.     this->wartosc = a;
10.   }
11. };

W przedstawionym kodzie Wezel ma wskaźniki na (4.) lewego i (5.) prawego potomka. Ich początkowe wartości to NULL, ponieważ wskazywane elementy jeszcze nie istnieją. Potem (6.) domyślna wartość to też NULL. (8. - 10.) Do klasy został dodany prosty konstruktor, który pozwala na utworzenie węzła z konkretną wartością.

Drzewo

Choć może się to okazać zaskakujące to klasa DrzewoBST musi przechowywać tylko jedną zmienną - węzeł, który jest podstawą całego drzewa. Jest to możliwe dzięki temu, że każdy następny węzeł wie jakie węzły po nim następują.

1.   Wezel<T> *korzen = NULL;

Dodawanie elementów

Chcą dodać element do drzewa użytkownik podaje jedynie pewną wartość typu T. Procesem tworzenia węzła i wyszukiwaniem pozycji zajmie się program. Funkcja dodająca została podzielona na dwie części: widoczną dla użytkownika, którą może wywołać i niewidoczną, ponieważ użytkownik nie powinien jej używać, aby zachować spójność struktury.

1.   void dodajWartosc(T a) {
2.     if (korzen) {
3.       dodajWartosc(korzen, a);
4.     } else {
5.       korzen = new Wezel<T>(a);
6.     }
7.   }

Dostępna do wywołania funkcja dla użytkownika sprawdza czy drzewo jest puste. Jesli tak to wartość korzenia ustala na dodawaną, a jeśli nie to rozpoczyna rekurencyjne poszukiwania miejsca dodania wstawianej wartości. Służy do tego ukryta funkcja o tej samej nazwie, ale która przyjmuje dodatkowo węzeł dla którego chcemy ustalić wartość potomka.

1.   void dodajWartosc(Wezel<T> *w, T a) {
2.     if (w->wartosc > a) {
3.       if (!w->lewy) {
4.         w->lewy = new Wezel<T>(a);
5.       } else {
6.         dodajWartosc(w->lewy, a);
7.       }
8.     } else {
9.       if (!w->prawy) {
10.         w->prawy = new Wezel<T>(a);
11.       } else {
12.         dodajWartosc(w->prawy, a);
13.       }
14.     }
15.   }

Dla węzła jest wykonane porównanie czy powinien znaleźć się po lewej czy po prawej stronie węzła czy po lewej. Niezależnie od wybranej strony trzeba sprawdzić czy z danej strony nie istnieje już węzeł, bo jeśli nie to można tam dodać nowy z wstawianą wartością. Jednak jeśli już istnieje to trzeba dla tego potomka wywołać dodawanie wartości.

Przedstawiona część kodu gwarantuje, że zawsze po lewej stronie od węzła znajdą się wartości od niego mniejsze, a na prawo większe.

Wypisanie drzewa

Część kodu, która pozwala na utworzenie drzewa została napisana, ale przydałoby się teraz jednak sprawdzić poprawność działania programu. Jednym ze sposobów jest prześledzenie działania programu z poziomu debugowania. Jednak lepszym pomysłem byłoby wypisanie drzewa. Jednak jak to osiągnąć ?

Jednym z pomysłów jest wypisanie każdego węzła w postaci: wartości węzła, a potem kolejno kolejnych wartości z lewego i prawego potomka zamykając je w nawiasy kwadratowe. Przykładowo takie drzewo:

Przykładowe drzewo

Zostało by wypisane jako: "6 [4 [3 [][]][5 [][]]][8 [][]]". Oczywiście zapis ten byłby czytelniejszy, gdyby nie wypisywać pustych węzłów: "6[4[3][5]][8]". Ponownie kod został podzielony na dwie części. Dla użytkownika jest widoczna bezparametrowa funkcja wypisz():

1.   void wypisz() {
2.     wypisz(korzen);
3.   }

Właściwa część kodu przyjmuje, który węzeł ma zostać wypisany i przedstawia się następująco:

1.   void wypisz(Wezel<T> *w) {
2.     if (w != NULL) {
3.       cout << w->wartosc << " [";
4.       wypisz(w->lewy);
5.       cout << "][";
6.       wypisz(w->prawy);
7.       cout << "]";
8.     }
9.   }

Testowanie funkcji

W celu przetestowania kodu wystarczy poniższy kod:

1. int main() {
2.   DrzewoBST<int> drzewo;
3.   drzewo.dodajWartosc(5);
4.   drzewo.dodajWartosc(4);
5.   drzewo.dodajWartosc(8);
6.   drzewo.dodajWartosc(3);
7.   drzewo.wypisz();
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja