Бинарное дерево поиска (Binary Search Tree, BST) — это особый вид бинарного дерева данных, в котором каждый узел содержит ключ (значение), и для каждого узла выполняется следующее свойство:

Ключи всех узлов в левом поддереве меньше ключа данного узла.
Ключи всех узлов в правом поддереве больше ключа данного узла.
Левое и правое поддеревья также являются бинарными деревьями поиска.

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

Пример узла:

javascript

Основные операции:

Поиск: Начинается с корня. Если искомое значение меньше ключа текущего узла, переходим в левое поддерево; если больше — в правое; если равно — найден.
Вставка: Аналогично поиску, но когда достигается подходящее место (null), создается новый узел.
Удаление: Наиболее сложная операция. Зависит от количества потомков удаляемого узла (0, 1 или 2). При удалении узла с двумя потомками обычно заменяется наименьшим элементом из правого поддерева или наибольшим из левого.

Бинарные деревья поиска используются для создания словарей, множеств и для эффективной сортировки данных (сортировка деревом). Для поддержания сбалансированности и гарантии логарифмического времени операций используются самобалансирующиеся варианты, такие как AVL-деревья или красно-черные деревья.

Что такое бинарное дерево поиска?