Drzewo wyszukiwania - Search tree
W informatyce , o drzewo wyszukiwania jest strukturą danych drzewa wykorzystywane do lokalizowania określonych kluczy w zestawie. Aby drzewo funkcjonowało jako drzewo wyszukiwania, klucz dla każdego węzła musi być większy niż klucze w poddrzewach po lewej stronie i mniejszy niż klucze w poddrzewach po prawej stronie.
Zaletą drzew wyszukiwania jest ich wydajny czas wyszukiwania, biorąc pod uwagę, że drzewo jest rozsądnie zrównoważone, co oznacza, że liście na obu końcach mają porównywalną głębokość. Istnieją różne struktury danych drzewa wyszukiwania, z których kilka umożliwia również wydajne wstawianie i usuwanie elementów, których operacje muszą następnie utrzymywać równowagę drzewa.
Drzewa wyszukiwania są często używane do implementacji tablicy asocjacyjnej . Algorytm drzewa wyszukiwania używa klucza z pary klucz-wartość do znalezienia lokalizacji, a następnie aplikacja przechowuje całą parę klucz-wartość w tej konkretnej lokalizacji.
Rodzaje drzew
Drzewo wyszukiwania binarnego
Drzewo wyszukiwania binarnego to struktura danych oparta na węzłach, w której każdy węzeł zawiera klucz i dwa poddrzewa, lewe i prawe. Dla wszystkich węzłów klucz lewego poddrzewa musi być mniejszy niż klucz węzła, a klucz prawego poddrzewa musi być większy niż klucz węzła. Wszystkie te poddrzewa muszą kwalifikować się jako drzewa wyszukiwania binarnego.
Najgorsza złożoność czasowa przy przeszukiwaniu drzewa wyszukiwania binarnego to wysokość drzewa , która może być tak mała jak O(log n) dla drzewa zawierającego n elementów.
B-drzewo
B-drzewa są uogólnieniem binarnych drzew wyszukiwania, ponieważ mogą mieć zmienną liczbę poddrzew w każdym węźle. Chociaż węzły podrzędne mają wstępnie zdefiniowany zakres, niekoniecznie będą wypełnione danymi, co oznacza, że drzewa B mogą potencjalnie zmarnować trochę miejsca. Zaletą jest to, że drzewa B nie muszą być ponownie równoważone tak często, jak inne drzewa samobalansujące .
Ze względu na zmienny zakres długości ich węzłów, B-drzewa są zoptymalizowane pod kątem systemów odczytujących duże bloki danych, są również powszechnie stosowane w bazach danych.
Złożoność czasowa przeszukiwania B-drzewa wynosi O(log n).
(a,b)-drzewo
Drzewo (a,b) to drzewo wyszukiwania, w którym wszystkie jego liście mają tę samą głębokość. Każdy węzeł ma co najmniej jedno dziecko i co najwyżej b dzieci, podczas gdy korzeń ma co najmniej 2 dzieci i co najwyżej b dzieci.
a i b można określić za pomocą następującego wzoru:
Złożoność czasowa przeszukiwania drzewa (a,b) wynosi O(log n).
Trójargumentowe drzewo wyszukiwania
Trójskładnikowe drzewo wyszukiwania to rodzaj drzewa, które może mieć 3 węzły: niskie dziecko, równe dziecko i wysokie dziecko. Każdy węzeł przechowuje pojedynczy znak, a samo drzewo jest uporządkowane w taki sam sposób, jak drzewo wyszukiwania binarnego, z wyjątkiem możliwego trzeciego węzła.
Wyszukiwanie w trójskładnikowym drzewie wyszukiwania polega na przekazaniu ciągu w celu sprawdzenia, czy zawiera go jakakolwiek ścieżka.
Złożoność czasowa przeszukiwania zrównoważonego trójskładnikowego drzewa poszukiwań wynosi O(log n).
Algorytmy wyszukiwania
Wyszukiwanie określonego klucza
Zakładając, że drzewo jest uporządkowane, możemy wziąć klucz i spróbować go zlokalizować w drzewie. Poniższe algorytmy są uogólnione dla drzew wyszukiwania binarnego, ale ten sam pomysł można zastosować do drzew o innych formatach.
Rekursywny
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node
Wielokrotny
searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right
Wyszukiwanie min i max
W posortowanym drzewie minimum znajduje się w węźle najbardziej wysuniętym na lewo, a maksimum w węźle najbardziej wysuniętym na prawo.
Minimum
findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key
Maksymalny
findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key