binarne drzewo poszukiwań

Binarne drzewo poszukiwań (ang. Binary Search Tree, BST) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach mniejszych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Koszt wykonania podstawowych operacji w drzewie BST (wstawienie, wyszukanie, usunięcie węzła) jest proporcjonalny do wysokości drzewa ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w notacji Landaua zapisuje się Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów zatem dla drzewa o węzłach optymistyczny koszt każdej z podstawowych operacji wynosi Z drugiej strony drzewo skrajnie niezrównoważone ma wysokość porównywalną z liczbą węzłów (w skrajnym przypadku drzewa zdegenerowanego do listy wartości te są równe: ), z tego powodu koszt pesymistyczny wzrasta do Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości kluczy posortowanych niemalejąco. Binarne drzewa wyszukiwań często stosuje się w zadaniach, w których wymagane jest względnie szybkie sortowanie lub wyszukiwanie elementów, na przykład różnego rodzaju słowniki, kolejki priorytetowe.