Помните бинарный поиск? Вы разрезаете отсортированный список на две половины, а затем сравниваете элемент в середине списка с элементом, который пытаетесь найти. Если средний элемент больше вашего, вы повторяете процесс на половине с меньшими значениями. Если середина меньше вашего предмета, то вы повторяете это на второй половине. С помощью этого метода вы можете разделить список пополам, пока не найдете свой предмет.

Это очень эффективный алгоритм поиска. Однако использование традиционного списка имеет некоторые недостатки. Скажем, вы хотите вставить элемент в середине. После этого вам нужно будет переместить каждый элемент в списке вправо на одно место. Удаление элемента перемещает все впоследствии на один пробел влево.

Как мы можем уменьшить этот удар по эффективности? Мы можем использовать совершенно новую структуру данных, созданную специально для наших целей.

Бинарные деревья поиска

Двоичное дерево поиска (сокращенно BST) – это рекурсивно определенная структура данных. Если вы когда-либо видели дерево файлов или что-то подобное, это должно показаться вам знакомым. Однако есть одно ключевое отличие: вам разрешено не более двух поддеревьев. И правила, по которым узлы могут куда идти, очень точны:

  • BST имеет единственный узел root вверху. Этот узел не имеет родителей.
  • Этот корневой узел может иметь до двух поддеревьев в качестве дочерних: одно слева и одно справа. Эти дети также BST.
  • У левого поддерева корневое значение меньше, чем у родителя.
  • Корневое значение правого поддерева больше, чем у родителя.

Имейте в виду, что BST содержит другие BST. Взгляните на определение ниже:

class BinarySearchTree:
   ```
   root: Any
   left: Union[BinarySearchTree, None]
   right: Union[BinarySearchTree, None]
   ```

(Примечание. Хотя корень может быть чем угодно, это должна быть какая-то сортируемая структура, такая как целые числа или строки)

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

Узел также может иметь только одно поддерево либо с левой, либо с правой стороны.

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

Вставка также проста. Начните с корневого узла, затем сравните его значение с вашим новым элементом. Если корень меньше, то переходим в правое поддерево. В противном случае перейдите в левое поддерево. Повторяйте этот процесс, пока не достигнете пустого поддерева. Замените пустое поддерево новым элементом.

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

********