Drzewo wyszukiwania to struktura danych używana w programowaniu komputerowym do przechowywania i organizowania listy danych. Każde drzewo wyszukiwania składa się z uporządkowanego zestawu węzłów. Węzły te mogą być połączone z zerem lub większą liczbą innych węzłów. Poszczególne węzły zawierają pewne dane, a także linki do dowolnych innych węzłów. Dane zawarte w węzłach drzewa są bardzo często uporządkowane w taki sposób, aby umożliwić wydajnym algorytmom wyszukiwanie, z łatwością wstawiaj i usuwaj węzły.
Węzły drzewa wyszukiwania są opisane czterema ważnymi terminami: wierzchołek drzewa, w którym znajduje się pierwszy węzeł, nazywany jest korzeniem. Jeśli węzeł zawiera linki do sub -węzły, ten węzeł jest znany jako rodzic. Węzły znajdujące się poniżej rodzica nazywane są dziećmi, a każdy węzeł, który nie ma węzłów podrzędnych, nazywany jest liściem. węzeł główny jest identyfikowany, ponieważ nie ma rodzica, a węzły liści nie będą miały dzieci.
Program może poruszać się po drzewie w poszukiwaniu danych, zaczynając od konkretnego węzła, wykonując sprawdzenie warunkowe, a następnie przechodząc do następnego węzła logicznego, jeśli nie ma wymaganych danych. , to wyszukiwanie może zająć różną ilość czasu. Jeśli drzewo wyszukiwania jest zorganizowane podczas procesu dodawania i usuwania węzłów, wyszukiwanie może być bardzo szybkie. Po złożeniu drzewa losowo, jest nieposortowany lub zezwala na wielu rodziców, wyszukiwanie może zająć bardzo dużo czasu.
Jednym z czynników wpływających na użycie drzew wyszukiwania jest kwestia równowagi.Drzewo zrównoważone to takie, w którym zarówno prawe, jak i lewe dzieci węzła głównego zawierają albo tę samą głębokość węzłów podrzędnych, albo znajdują się w liczbie jednego węzła siebie. Głębokość drzewa to liczba węzłów od najniższego liścia drzewa do korzenia. Niezrównoważone drzewo może mieć wszystkie węzły tylko po jednej stronie lub mieć wszystkie węzły ułożone liniowo bez gałęzi.Gdy głębokość drzewa rośnie, szybkość algorytmów wyszukiwania może drastycznie spaść.
Istnieją pewne typy drzew wyszukiwania, które są opisane jako samobalansujące.Drzewa te wykorzystują operacje, takie jak rotacja drzew, aby pomóc utrzymać równowagę przy jednoczesnym zachowaniu kolejności danych w liściach. rotacje drzew mogą spowolnić program podczas dodawania i usuwania węzłów, czemu przeciwdziała prędkość, z jaką dane mogą być pobierane.
Chociaż istnieje wiele typów drzew wyszukiwania, najpowszechniejszą strukturą danych jest drzewo wyszukiwania binarnego.Ten typ danych składa się z węzłów, z których każdy ma od zera do dwóch węzłów podrzędnych.Istnieje tylko jeden węzeł główny, a wszystkie liście w drzewie są uporządkowane od lewej do prawej w rosnących wartościach zgodnie z danymi, które przechowują.Istnieje wiele algorytmów dla drzew wyszukiwania binarnego, które mogą sprawiają, że zamawianie danych jest bardzo łatwe.
Nie ma jednej standardowej implementacji dla węzłów drzewa wyszukiwania. Węzły mogą być reprezentowane przez szeroką gamę struktur danych. Tablice tablic mogą być używane, podobnie jak mnożenie połączonych list. Często a Drzewo wyszukiwania wykorzystuje niestandardową strukturę danych, która ma pomóc w zakończeniu niezbędnych operacji wymaganych przez program.Niektóre standardowe biblioteki programistyczne zawierają nawet własne wewnętrzne implementacje drzew wyszukiwania.