На этом шаге мы дадим определение такого дерева.

Определение (по [1, с.499]).: Бинарное дерево поиска с ключами - это бинарное дерево, с каждым из внутренних узлов которого связан ключ, причём ключ в любом узле больше (или равен) ключам и во всех узлах левого поддерева этого узла и меньше (или равен) ключам во всех узлах правого поддерева этого узла.

⁽¹⁾Седжвик Р. Фундаментальные алгоритмы C++. Анализ. Структуры данных. Сортировка. Поиск. - К.: ДиаСофт, 2001. - 688 с.

На следующем шаге мы рассмотрим случайные бинарные деревья поиска.