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

Как показано на рисунке ниже, <u>двоичное дерево поиска (binary search tree)</u> удовлетворяет следующим условиям.

1. Для корневого узла значения всех узлов в левом поддереве $<$ значения корневого узла $<$ значения всех узлов в правом поддереве.
2. Левое и правое поддеревья любого узла также являются двоичными деревьями поиска, т. е. также удовлетворяют условию `1.`.

![Двоичное дерево поиска](../assets/binary_search_tree.png)

## Операции с двоичным деревом поиска

Мы инкапсулируем двоичное дерево поиска в класс `BinarySearchTree` и объявляем переменную-член `root`, указывающую на корневой узел дерева.

### Поиск узла

Для заданного значения целевого узла `num` можно выполнить поиск, используя свойства двоичного дерева поиска. Как показано на рисунке ниже, мы объявляем узел `cur`, начиная с корневого узла `root` двоичного дерева, и циклически сравниваем значение узла `cur.val` с `num`.

- Если `cur.val < num`, это означает, что целевой узел находится в правом поддереве `cur`, поэтому выполняем `cur = cur.right`.
- Если `cur.val > num`, это означает, что целевой узел находится в левом поддереве `cur`, поэтому выполняем `cur = cur.left`.
- Если `cur.val = num`, это означает, что целевой узел найден, выходим из цикла и возвращаем этот узел.

=== "<1>"
    ![Пример поиска узла в двоичном дереве поиска](../assets/bst_search_step1.png)

=== "<2>"
    ![bst_search_step2](../assets/bst_search_step2.png)

=== "<3>"
    ![bst_search_step3](../assets/bst_search_step3.png)

=== "<4>"
    ![bst_search_step4](../assets/bst_search_step4.png)

Операция поиска в двоичном дереве поиска работает по тому же принципу, что и алгоритм бинарного поиска: в каждом раунде исключается половина случаев. Количество циклов не превышает высоты двоичного дерева, когда двоичное дерево сбалансировано, используется $O(\log n)$ времени. Пример кода приведен ниже:

```src
[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{search}
```

### Вставка узла

Для заданного элемента `num`, который необходимо вставить, чтобы сохранить свойство двоичного дерева поиска "левое поддерево < корневой узел < правое поддерево", процесс вставки выглядит следующим образом.

1. **Поиск позиции для вставки**: аналогично операции поиска, начиная с корневого узла, циклически выполняем поиск вниз в зависимости от соотношения между значением текущего узла и `num`, пока не выйдем за пределы листового узла (достигнем `None`), после чего выходим из цикла.
2. **Вставка узла в эту позицию**: инициализируем узел `num` и помещаем этот узел на место `None`.

![Вставка узла в двоичное дерево поиска](../assets/bst_insert.png)

В реализации кода необходимо обратить внимание на следующие два момента.

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

```src
[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{insert}
```

Как и при поиске узла, вставка узла использует $O(\log n)$ времени.

### Удаление узла

Сначала находим целевой узел в двоичном дереве, затем удаляем его. Аналогично вставке узла, нам необходимо обеспечить, чтобы после завершения операции удаления свойство двоичного дерева поиска "левое поддерево < корневой узел < правое поддерево" по-прежнему выполнялось. Поэтому, в зависимости от количества дочерних узлов целевого узла, мы различаем 3 случая: 0, 1 и 2, и выполняем соответствующую операцию удаления узла.

Как показано на рисунке ниже, когда степень удаляемого узла равна $0$, это означает, что узел является листовым и может быть удален напрямую.

![Удаление узла в двоичном дереве поиска (степень 0)](../assets/bst_remove_case1.png)

Как показано на рисунке ниже, когда степень удаляемого узла равна $1$, достаточно заменить удаляемый узел его дочерним узлом.

![Удаление узла в двоичном дереве поиска (степень 1)](../assets/bst_remove_case2.png)

Когда степень удаляемого узла равна $2$, мы не можем удалить его напрямую, а должны использовать другой узел для замены этого узла. Чтобы сохранить свойство двоичного дерева поиска "левое поддерево $<$ корневой узел $<$ правое поддерево", **этим узлом может быть минимальный узел правого поддерева или максимальный узел левого поддерева**.

Предположим, мы выбираем минимальный узел правого поддерева (следующий узел в симметричном обходе), тогда процесс удаления выглядит следующим образом.

1. Находим узел, следующий за удаляемым узлом в "последовательности симметричного обхода", обозначим его как `tmp`.
2. Заменяем значение удаляемого узла значением `tmp` и рекурсивно удаляем узел `tmp` в дереве.

=== "<1>"
    ![Удаление узла в двоичном дереве поиска (степень 2)](../assets/bst_remove_case3_step1.png)

=== "<2>"
    ![bst_remove_case3_step2](../assets/bst_remove_case3_step2.png)

=== "<3>"
    ![bst_remove_case3_step3](../assets/bst_remove_case3_step3.png)

=== "<4>"
    ![bst_remove_case3_step4](../assets/bst_remove_case3_step4.png)

Операция удаления узла также использует $O(\log n)$ времени, где поиск удаляемого узла требует $O(\log n)$ времени, получение узла-преемника в симметричном обходе требует $O(\log n)$ времени. Пример кода приведен ниже:

```src
[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{remove}
```

### Упорядоченность симметричного обхода

Как показано на рисунке ниже, симметричный обход двоичного дерева следует порядку обхода "левый $\rightarrow$ корневой $\rightarrow$ правый", а двоичное дерево поиска удовлетворяет соотношению размеров "левый дочерний узел $<$ корневой узел $<$ правый дочерний узел".

Это означает, что при выполнении симметричного обхода двоичного дерева поиска всегда сначала обходится следующий наименьший узел, что приводит к важному свойству: **последовательность симметричного обхода двоичного дерева поиска является возрастающей**.

Используя свойство возрастания симметричного обхода, мы можем получить упорядоченные данные в двоичном дереве поиска всего за $O(n)$ времени, без необходимости выполнения дополнительных операций сортировки, что очень эффективно.

![Последовательность симметричного обхода двоичного дерева поиска](../assets/bst_inorder_traversal.png)