Drzewo BST (binary search tree) jest drzewem binarnym. Oprócz pola wartości drzewo BST posiada jeszcze dwa pola: L i P, wskazujące odpowiednio na lewy i prawy następnik. Drzewo BST ma szczególną własność:

• jeżeli element drzewa znajduje się w lewej gałęzi to jest mniejszy od swego poprzednika
• jeżeli element drzewa znajduje się w prawej gałęzi to jest większy od swego poprzednika

Oto przykładowe drzewo BST:

Przeszukiwanie drzewa:

• Wzdłużne - preorder: korzeń, lewe poddrzewo, prawe poddrzewo.
• Poprzeczne - inorder: lewe poddrzewo, korzeń, prawe poddrzewo.
• Wsteczne - postorder: lewe poddrzewo, prawe poddrzewo, korzeń.

Dodwanie elementów:
Jeśli drzewo BST jest puste (korzeń=nil) należy wstawić element (nie porównujemy go z innymi), w przeciwnym wypadku porównujemy wartość elementu z następnikami każdego węzła (zaczynając od korzenia). Jeżeli wartość elementu jest niewiększa od wartości porównywanego wierzchołka to przechodzimy do lewego następnika, w przeciwnym razie przechodzimy do prawego następnika. Krok ten powtarzamy aż znajdziemy dla naszego elementu odpowiedznie miejsce, tzn. gdy następnik, do którego powinniśmy iść jest pusty (nil). Następnie wstawiamy element jako odpowiedni następnik (prawy, jeśli element jest większy od węzła, lewy jeśli niewiększy).

Usuwanie elementów:
Jeżeli usuwany element nie ma następników to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem usuwanego elementu. Jeśli element ma dwa następniki można go usunąć na dwa sposoby:

• połączyć poprzednik elementu z wierzchołkiem o najmniejszej wartości z prawego poddrzewa usuwanego
• połączyć poprzednik elementu z wierzchołkiem o największej wartości z lewego poddrzewa

Usuwanie drzewa:
Można to zrobić na dwa sposoby: od końca, schodząc za każdym razem od korzenia lub od korzenia. Ta druga metoda jest znacznie szybsza, wymaga jednak zastosowania stosu, na którym umieszczamy następniki usuwanego elementu. Po usunięciu elementu zdejmujemy ze stosu następny do usunięcia, umieszczamy na stosie jego następniki itd...