Деревья поиска. Операция поиска элемента.

Гоша: Так как же деревья помогают искать?
Тимофей: Частный случай этой структуры данных — дерево поиска. Именно оно помогает искать элементы.
Двоичное дерево поиска (по англ. binary search tree, BST) — двоичное дерево, для которого выполнены следующие условия:
  • Левое и правое поддеревья, если существуют, являются двоичными деревьями поиска.
  • Под произвольным узлом Х слева располагаются узлы со значениями меньше Х.
  • Под произвольным узлом Х справа располагаются узлы со значениями больше Х.
image
Данное определение справедливо для деревьев, в которых нет повторяющихся элементов. В случае, если наличие узлов с одинаковыми значениями допускается, равные элементы обычно относят к правому поддереву.
Применяют деревья поиска только в случае, если значения узлов сравнимы между собой.
image
Дано дерево поиска. Найдём в нём элемент 7:
image
  1. Сравниваем значение в корне с искомым элементом. 7 меньше 10. Следовательно, идём налево.
image
  1. Сравниваем искомое значение со значением левого потомка. 7 больше 5. Тогда идём направо.
image
  1. Сравниваем значение правого потомка рассмотренного узла с искомым элементом. 7 равно 7. Останавливаем поиск.
Если бы мы использовали такое дерево, ничего бы не получилось!
image
Гоша: А что, если искать элемент, которого в дереве нет?
Тимофей: Допустим, мы хотим найти элемент 9.
Первые два шага совпадут с примером, когда мы выполняли поиск 7.
А вот третий шаг отличается. При сравнении текущего узла с искомым — 7 с 9 — мы должны пойти направо. Но у листа 7 отсутствует правый потомок, то есть узел ссылается на Null. Поэтому мы сделаем вывод, что в этом дереве нет искомого элемента.
Гоша: Я понял! Все просто.
Посмотрите урок с разбором задач, а потом решите задачи A, E: https://contest.yandex.ru/contest/18996/problems/A/.