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.
Możliwe jest przeszukiwanie ... następnika, natomiast bez możliwości poprzednika, także jest to możliwe i da się to rozwiązać.
Bo z zasady posortowane drzewo :) rekurencyjnie przeszukująć nastepnika, jesteśmy wstanie przeszukać całe drzewo