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

O(log n) avg

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

Сигналы

двоичное дерево поиска: left < node < right в каждом узлевставка/удаление/поиск с сохранением порядка данныхпроверить BST / k-й наименьший / симметричный обход даёт отсортированную последовательностьближайшее значение или запрос по диапазону на множестве, которое меняется со временеммассив заранее не дан, значения приходят по одному

Шаблон

function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

Похоже, но не то

Бинарный поиск по отсортированному массиву: BST это динамическое отсортированное множество: поддерживает вставку и удаление с сохранением порядка, а симметричный обход всегда даёт текущую отсортированную последовательность. Обычный бинарный поиск предполагает статичный отсортированный массив, который не меняется во время поиска.

n узлов, дерево примерно сбалансировано -> O(log n) в среднем на поиск/вставку/удаление, потому что каждое сравнение отбрасывает целое поддерево. В худшем случае вырождается в O(n), если дерево превращается в цепочку (например, при вставке уже отсортированных данных по порядку).

Изучить этот паттерн