Implementacja drzewa BST w Javie

Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie

Nasza implementacja drzewa BST składa się z dwóch klas.

  • Wezel – jest klasą wewnętrzną. Reprezentuje pojedynczy węzeł w drzewie. Przechowywanym kluczem jest wartość int.
  • Drzewo – zawiera algorytmy dodawania, usuwania, wyświetlania elementów, odnajdywania poprzednika i następnika węzła oraz przechowuje korzeń. Jest klasą zewnętrzną.

Drzewa BST są ważną strukturą danych. Pozwalają o wiele skrócić czas wyszukiwania elementów, co jest szczególnie zauważalne przy dużych zbiorach. Oczywiście zakładając, że drzewo jest zrównoważone – w przeciwnym wypadku liczba operacji może wzrosnąć do poziomu zwykłej listy. Dużo lepszą wydajność zapewnią drzewa AVL lub drzewa czerwono-czarne. Te struktury poprzez rotacje potrafią zapewnić zrównoważenie poziomu obu poddrzew korzenia. Aby jednak je poznać warto najpierw poznać dokładnie drzewa BST, gdyż ta wiedza jest niezbędna, aby potem stosować dodatkowe zasady umieszczania węzłów.

Teoretyczna część znajduje się w naszym artykule odnośnie drzew BST. Tutaj skupimy się na praktycznej implementacji podanych tam algorytmów.

Klasa Drzewo

Wewnętrzna klasa Wezel

Klasa Wezel przechowuje informację o dwóch potomkach, o rodzicu oraz klucz. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Drzewo, gdyż i tak nie wykorzystamy jej nigdzie indziej.

Pola

Obiekt klasy Wezel zawiera trzy referencje:

  • do lewego potomka,
  • do prawego potomka,
  • oraz do rodzica.

Dodatkowym polem jest przechowywana wartość czyli zmienna key.

Konstruktor

Inicjuje dane – referencje do innych węzłów na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Drzewo

Obiekt klasy Drzewo przechowuje referencję do korzenia (ang. root). Zawiera również niezbędne algorytmy, takie jak:

  • dodawanie elementów do drzewa,
  • usuwanie elementów z drzewa,
  • szukanie elementu o konkretnej wartości,
  • znalezienie największej wartości w drzewie,
  • znalezienie najmniejszej wartości w drzewie,
  • wskazanie następnika węzła,
  • wskazanie poprzednika węzła.

Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

System zbierania nieużytków (ang. Garbage collector)

W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Wystarczy odłączyć usuwany obiekt od struktury drzewa.