Drzewa poszukiwań binarnych BST

Drzewo – definicja

Pojęcie drzewa wywodzi się z teorii grafów. Jest to graf nieskierowany, acykliczny i spójny. Oznacza to, że do każdego wierzchołka prowadzi krawędź, a graf nie posiada cykli (każde dwa wierzchołki łączy tylko jedna droga prosta). Wpis jest częścią artykułów o kolekcjach w Javie.

Drzewo nieskierowany graf spójny, acykliczny
Drzewo – nieskierowany graf spójny, acykliczny

Poniżej pokażemy przykłady grafów, które nie spełniają definicji drzewa.

Graf niespójny - nie spełnia definicji drzewa
Graf niespójny – nie spełnia definicji drzewa
Graf cykliczny- nie spełnia definicji drzewa
Graf cykliczny – nie spełnia definicji drzewa

Drzewo w kontekście informatyki jest strukturą danych, która w sposób uporządkowany przechowuje dane, dzięki czemu ułatwia do nich dostęp (zmniejsza liczbę operacji, które są potrzebne, aby dostać się do elementu).

Budowa drzewa

Drzewo składa się z wierzchołków (węzłów), z których można wyróżnić.

  • Korzeń – pierwszy element w drzewie.
  • Liście – wierzchołki nieposiadające potomstwa.
Drzewo budowa - korzenie, liście
Drzewo budowa – korzenie, liście

Każdy wierzchołek znajduje się na pewnym poziomie (korzeń na poziomie 0). Dzieci znajdują się zawsze poziom wyżej. Wysokość drzewa określa najwyższy poziom wierzchołka (poziom + 1 ze względu na korzeń).

Drzewa binarne

Specyficzną strukturą są drzewa, które posiadają co najwyżej dwóch potomków. Wtedy wyróżniamy lewego i prawego potomka.

Binarne drzewo poszukiwań (drzewo BST)

BST to skrót od Binary Search Tree, w których lewy potomek zawsze zawiera wartości mniejsze niż rodzic, a prawy większe. Tyczy się to całego poddrzewa.

Drzewo jest skomplikowaną strukturą, która wymaga wiele pracy, jednak trud włożony w implementację wynagradza logarytmiczny czas dostępu do danych (w optymistycznym wariancie). Drzewo pozwala na różne operacje w tym dodawanie i usuwanie elementów, które mogą zdegenerować drzewo nawet do postaci listy, a wtedy złożoność wyszukiwania zbliża się do liniowej. Aby drzewo zachowało swoje zalety należy dbać, aby poziom prawego i lewego poddrzewa był w miarę możliwości równy.

Należy pamiętać, że każdy element lewego poddrzewa jest mniejszy niż rodzic, a każdy element prawego poddrzewa jest większy.

Budowa węzła

Każdy węzeł posiada klucz (przechowywane dane) oraz trzy referencje – na lewe i prawe dziecko oraz rodzica.

Operacje do wykonania na drzewach BST

Na drzewach można wykonywać różne operacje, ale na razie skupimy się na podstawowych czyli: odnalezieniu węzła o podanym kluczu, wstawieniu węzła oraz usuwanie elementu. Dodatkowo możemy łatwo zaimplementować zwrócenie największego oraz najmniejszego elementu. Aby wypisać wszystkie elementy z drzewa można wykorzystać algorytm przechodzenia wzdłuż lub wszerz.

W celu optymalizacji warto zaimplementować rotowanie drzew, które zmniejsza różnice między poziomami lewego i prawego poddrzewa.

Dodawanie elementu do drzewa

Przed wykonaniem operacji należy zastanowić się nad różnymi przypadkami. Jeśli korzeń jest pusty, to taki element będzie ustawiony jako pierwszy element.

Drugie pytanie brzmi co z obiektem, który znajduje się już w drzewie? To zależne od implementacji, jednak w wielu przypadkach umieszczanie elementu o tej samej wartości raczej nie jest potrzebne i negatywnie by wpływało na wydajność struktury. W tym celu należy przeszukać drzewo zgodnie z algorytmem.

Jeżeli warunek unikalności jest spełniony i nie ma elementu, który chcemy wstawić należy utworzyć obiekt klasy Wezel, a następnie uzupełnić referencje rodzica. Ze względu na to, że nie mamy referencji do rodzica należy pamiętać, aby jej nie zgubić w trakcie przechodzenia przez drzewo.

Dodawanie węzła w drzewie BST
Dodawanie węzła w drzewie BST

Wyszukiwanie elementu w drzewie

Jest to stosunkowo prosta operacja. Jej algorytm mamy już zapisany w poprzednim podrozdziale na temat dodawania. Tym razem wyszukujemy po prostu elementu na podstawie podanego klucza, a następnie go zwracamy. Poniżej pokazujemy jak działa wyszukiwanie elementu w drzewie BST.

Wyszukiwanie węzła w drzewie BST
Wyszukiwanie węzła z wartością 12 w drzewie BST

Usuwanie elementów z drzewa

Usuwanie to zdecydowanie najtrudniejsza czynność do wykonania w drzewach, gdyż można przez przypadek przerwać spójność grafu.

Najprostszym przypadkiem jest usuwanie elementu, który jest liściem – po prostu usuwamy jego referencję w rodzicu. W każdym innym przypadku wymagane jest przeorganizowane struktury drzewa.

Usuwanie węzła (liścia) w drzewie BST
Usuwanie węzła (liścia) o wartości 12 w drzewie BST

Kolejny przypadek jest taki, że usuwamy, element, który ma jedno dziecko. Wtedy należy wstawić dziecko w miejscu rodzica.

Usuwanie węzła (jeden potomek) w drzewie BST
Usuwanie węzła (jeden potomek) o wartości 15 w drzewie BST

Najbardziej złożonym wariantem jest usunięcie elementu, który ma dwoje dzieci. Wtedy na jego miejsce należy umieścić poprzednik lub następnik. Wybór można podjąć ze względu na równoważenie drzewa i pobrać element z tej strony, po której w poddrzewie znajduje się więcej poziomów.

Usuwanie węzła (dwóch potomków) w drzewie BST
Usuwanie węzła (ma dwóch potomków) o wartości 15 w drzewie BST

Przykładowa implementacja drzewa BST.