Двоичное дерево поиска.

Двоичное дерево поиска представляет собой бинарное дерево, обладающее следующим свойством. Значение любого из узлов L₁, L₂, L₃, …, L_n левого поддерева, выходящего из некоторого корня K, всегда меньше значения самого этого корня: Value(L_i) < Value(K), тогда как отношение узлов R₁ , R₂, R₃, …, R_n правого поддерева к корню определяется нестрогим неравенством: Value(R_i) >= Value(K). Ниже изображен пример двоичного дерева поиска.

Здесь из корня, значение которого 10, выходят два поддерева, причем все левые элементы меньше правых и самого корня, а правые, соответственно, больше. Такое следование продолжается и на следующих уровнях.

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

• если дерево не содержит в себе элементов, то остановить поиск
• иначе сравнить искомый элемент (ключ) с корнем:
  • если значение ключа равно значению корня – поиск завершен, иначе
  • если значение ключа больше значения корня – искать в правой части, иначе
  • если значение ключа меньше значения корня – искать в левой части.

Эти действия выполняются до того момента, когда элемент будет найден, либо окажется что он вовсе отсутствует.

Рассмотренный метод для изображенного на рисунке выше бинарного дерева поиска, будет работать по такому сценарию. Допустим, значение ключа равно 13, и нужно найти узел с тем же значением. Вначале сравнивается ключ с корнем, значение которого 10. Так как 13 больше 10, поэтому далее для поиска следует выбрать правую ветку дерева, ведь элементы в ней больше 10, что известно из основного свойства бинарного дерева поиска. Далее поиск как бы переходит на новое дерево, которое является поддеревом изначального дерева. Тут ключ 13 сравнивается с узлом 16. Первое значение меньше, следовательно, поиск продолжается в левой части, и именно там расположен искомый элемент.

Помимо операции поиска, на двоичном дереве поиска эффективно применять операции добавления и удаления элемента. К тому же во многих ситуациях целесообразным оказывается обычное двоичное дерево переделать в дерево поиска, отсортировав его элементы одним из алгоритмов сортировки.