Популярным приложением бинарных деревьев, например, в технологиях баз данных является поиск требуемых элементов во входном потоке информации. Наиболее быстрый поисковый алгоритм основан на использовании бинарного дерева поиска. Дерево поиска - бинарное дерево, узлы которого упорядочены по ключам, таким образом, что ключ левого потомка меньше ключа предка, а ключ правого потомка больше ключа предка. Указанное соотношение порядка иллюстрирует следующий фрагмент бинарного дерева поиска.

Рис. 1.  Фрагмент бинарного дерева поиска.
В приведенном рисунке фрагмента бинарного дерева поиска ключ узла "В" меньше ключа узла "А", а ключ узла "С"больше ключа узла "А", т. е.
key(B) < key(A) и key(C) > key(A)

Правило сравнения ключей определяется типом ключевых данных. Скалярные (например, целочисленные) ключи упорядочиваются естественным образом по их величинам. Векторные ( например, символические) ключи упорядочиваются лексиграфически. Лексиграфический порядок образует упорядочивание векторов последовательно по величинам компонент.
Например. вектор V=(V1,..,Vj,..,Vp) лексиграфически больше, чем вектор W=(W1,..,Wj,..,Vp), если Vj=Wj при j<q и Vq>Wq.
Место очередного элемента в бинарном дереве поиска определяется путем сравнения его ключа с ключами существующих узлов, начиная с корня. В зависимости от результата каждого сравнения ключей, для продолжения поиска выбирается либо левое, либо правое поддерево текущего узла, если его ключ не равен ключу искомого образца. Поиск считается успешно завершенным, когда найден узел, ключ которого равен ключу искомого элемента. В противном случае, когда достигнут лист и нет соответствия образцу по ключу, необходимо расширить дерево поиска, добавив новый узел, либо в правую, либо в левую ветвь листа в зависимости от соотношения ключей. Методическая необходимость добавления новых узлов позволяет более строго называть рассмотренный алгоритм поиском по бинарному дереву со вставкой. Приведенное описание следует рассматривать как неформальное изложение данного алгоритма. Ниже рассмотрен классический пример поиска по бинарному дереву знаков зодиака.

Пример 1
На следующем рисунке изображено бинарное дерево поиска знаков зодиака, которое содержит 11 узлов с символическими векторными ключами, соответствующими латинским названиям знаков зодиака.

Рис. 2.  Бинарное дерево поиска знаков зодиака
Это бинарное дерево построено последовательной вставкой новых узлов в следующем порядке: capricorn, aquarius, pisces, aries, taurus, gemini, cancer, leo, virgo, libra, scorpio, начиная с корня. Поиск существующего в дереве знака libra (весы) образует следующую последовательность сравнения ключей:
libra > capricorn - поиск в правом поддереве capricorn;
libra < pisces - поиск в левом поддереве pisces;
libra > gemini - поиск в правом поддереве gemini;
libra > leo - поиск в правом поддереве leo;
libra = libra - поиск завершен успешно.
Поиск отсутствующего в дереве знака sagittarius (стрелец) образует следующая последовательность сравнения ключей:

sagittarius > capricirn - поиск в правом поддереве capricorn;
sagittarius > pisces - поиск в правом поддереве pisces;
sagittarius < taurus - поиск в левом поддереве taurus;
sagittarius < scorpio - поиск в левом поддереве scorpio;

Поскольку левое поддерево узла scorpio пусто, то для завершения поиска нужно добавить новый узел sagittaruis, который показан пунктиром на рисунке. Следует отметить, что если для поиска в бинарном дереве знаков зодиака использовать скалярные ключи, например, порядковые номера или диапазоны дат соответствующих знаков, то структура бинарного дерева и траектория поиска были бы иными , чем в рассмотренном варианте векторных ключей. Также другой результат был бы получен, если для ключей применить русские названия знаков зодиака, которые указаны на рисунке для перевода соответствующих латинских обозначений.