Деревья бинарного поиска

Определение

Дерево бинарного поиска (Binary Search Tree, BST) — это разновидность бинарного дерева, обладающая следующим свойством

• Для каждого узла все значения в его левом поддереве меньше значения в самом узле, а все значения в правом поддереве больше значения в узле.

Это свойство также подразумевает, что значения в BST должны быть уникальными.

Пример дерева бинарного поиска

    23
   /  \
  8    42
 / \     \
4   17    50
   /  \
  15   20

Операции и их сложность

В дереве бинарного поиска операции, такие как поиск, добавление и удаление, могут выполняться за O(log n) в среднем случае, где n — количество узлов в дереве. Это достигается благодаря использованию бинарного поиска.

Рассмотрим поиск значения 20 в приведённом дереве

1. Начинаем с корня: 23 > 20, значит, игнорируем правое поддерево.
2. Переходим в левое поддерево: 8 < 20, значит, игнорируем левое поддерево и двигаемся вправо.
3. Следующий узел: 17 < 20, снова идём вправо.
4. Наконец, находим 20.

Таким образом, поиск работает за O(log n) в среднем случае.

Худший случай

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

Дополнительный факт

Обход BST в порядке DFS (обход в глубину) с приоритетом "слева направо" (inorder traversal) обработает узлы в отсортированном порядке.

Задачи

https://leetcode.com/problems/range-sum-of-bst/description/
https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/
https://leetcode.com/problems/validate-binary-search-tree/description/
https://leetcode.com/problems/insert-into-a-binary-search-tree/description/
https://leetcode.com/problems/search-in-a-binary-search-tree/description/
https://leetcode.com/problems/all-elements-in-two-binary-search-trees/description/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
https://leetcode.com/problems/delete-node-in-a-bst/description/