Двоичное дерево поиска (BST)
Предпосылки: оценка сложности в O(…); рекурсия; бинарный поиск; дерево (корень, родитель, ребёнок, лист, высота); бинарное дерево (left/right, обходы — особенно in-order); массив и связный список (операции и их стоимость); указатели и ссылки; базовое чтение Ruby (классы, методы, блоки, массивы и хеши).
← Бинарное дерево | далее: B-дерево · Skip List →
Представим телефонную книгу на 10 000 контактов. Нужно быстро найти номер по имени, добавить новый контакт и удалить старый. Неотсортированный массив даёт O(1) на вставку (дописали в конец), но O(n) на поиск — в худшем случае 10 000 сравнений для одного запроса, потому что искать приходится перебором. Отсортированный массив ускоряет поиск до O(log n) бинарным поиском (деление отсортированного диапазона пополам), но теперь дорога вставка: чтобы новый элемент встал на своё место и порядок не сломался, все элементы правее него надо сдвинуть — это O(n). Получается развилка: либо быстрая вставка и медленный поиск, либо наоборот. BST обходит развилку — поиск, вставка и удаление выполняются за O(h), где h — высота дерева. Если дерево близко к сбалансированному (левая и правая половины примерно равны по высоте на каждом шаге), h ≈ log₂(n) ≈ 14 для 10 000 контактов; если вырождено (вытянуто в одну сторону, разобрано ниже) — h ≈ n.
Правило порядка в узлах
Чтобы дерево помогало искать, узлы расставлены не как попало, а по одному правилу, которое держится при каждой вставке и удалении (такое неизменное правило структуры называют инвариантом).
Инвариант BST: для каждого узла все значения в левом поддереве меньше значения узла, а все значения в правом поддереве — больше.
Значение, по которому идёт сравнение, — это ключ узла (для телефонной книги ключ — имя контакта). Ключи должны быть сравнимы между собой (есть операции «меньше» и «больше»). Что делать с равными ключами, решают заранее; в примере ниже дубликаты не добавляются.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13Из этого правила вытекает главное следствие: in-order обход BST даёт элементы в отсортированном порядке. In-order для каждого узла посещает сначала левое поддерево, потом сам узел, потом правое; а левое поддерево по инварианту целиком меньше узла, правое — целиком больше. Значит, на каждом узле сначала выводится всё меньшее, потом он сам, потом всё большее — то есть по возрастанию. Для дерева выше: 1, 3, 4, 6, 7, 8, 10, 13, 14.
Операции
Инвариант на каждом узле говорит, в какой из двух детей идти за нужным значением, а в каком его заведомо нет, — поэтому одну из двух сторон можно отбросить целиком. Если дерево сбалансировано, отброшенная сторона — примерно половина оставшихся узлов; в вырожденном дереве выигрыш меньше. На этом сужении области поиска держатся все три операции, и каждая начинает с корня.
Поиск. Сравниваем искомое значение с текущим узлом: равно — нашли; меньше — идём в левого ребёнка, больше — в правого; так до совпадения или до пустой ветки (значения нет). Найдём 4 в дереве выше: старт с корня 8, 4 < 8 — влево к 3, 4 > 3 — вправо к 6, 4 < 6 — влево к 4, совпадение. Четыре сравнения вместо девяти узлов перебором.
Вставка. Идём тем же спуском, что и поиск, но цель другая: поиск ищет существующий узел, а вставка должна найти место, где нужной ветки нет, — там и подвешивается новый узел. Добавим 5: 5 < 8 — влево к 3, 5 > 3 — вправо к 6, 5 < 6 — влево, но левого ребёнка у 6 нет — значит, 5 становится левым ребёнком 6. Инвариант сохранён: путь спуска как раз и гарантирует, что новое значение попало по правильную сторону от каждого предка.
Удаление разбивается на случаи по числу детей удаляемого узла, потому что от этого зависит, как сшить дерево обратно, не нарушив инвариант. Сначала находим узел спуском, затем:
Случай 1 — нет детей (лист): просто отцепляем узел от родителя (обнуляем ссылку, которая на него вела).
Случай 2 — один ребёнок: подвешиваем этого ребёнка на место удаляемого — ссылку родителя, которая вела на удаляемый узел, перенаправляем на его единственного ребёнка. Инвариант сохраняется: всё поддерево этого ребёнка уже лежало по ту же сторону от родителя, что и удаляемый узел, так что относительно предков диапазон значений не изменился.
Случай 3 — двое детей: здесь нельзя просто отцепить узел — оба поддерева надо куда-то деть. Решение — не удалять узел физически, а заменить его значение на ближайшее, после которого порядок не сломается. Такой замены два кандидата: наименьшее значение в правом поддереве (его называют successor — «следующий по порядку») или наибольшее в левом. Возьмём successor: спускаемся в правое поддерево и идём влево до упора (левее — только меньшие значения, а нам нужен минимум). Копируем его значение в удаляемый узел, а сам узел-successor затем удаляем. У successor по построению нет левого ребёнка (иначе тот был бы меньше и сам оказался бы минимумом), поэтому его удаление — это уже случай 1 или 2.
Удаляем 8: successor = 10, его значение
8 скопировано в корень, а
/ \ ==> старый узел 10 удалён (случай 2):
3 14 10
/ / \
10 3 14
\ /
13 13Сложность
Все три операции проходят путь от корня вниз, поэтому их сложность определяется высотой дерева. У удаления с двумя детьми путей даже два — сначала к удаляемому узлу, потом к его successor, — но оба идут сверху вниз и каждый ограничен высотой, так что в сумме это всё те же O(h).
| Операция | Лучший/средний | Худший |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
Оба столбца — это одно и то же O(h) при разной высоте: у сбалансированного дерева h ≈ log n (отсюда O(log n)), у вырожденного h ≈ n (отсюда O(n)). «Средний» случай близок к лучшему, потому что при случайном порядке вставок дерево обычно выходит близким к сбалансированному; «худший» отвечает за невезучий порядок.
И этот худший случай — не теоретическая редкость. Вырожденное дерево возникает, когда элементы выстраиваются в одну сторону и дерево вытягивается в цепочку — фактически в связный список, где у каждого узла только один ребёнок. Если контакты в телефонной книге добавлялись по алфавиту — Alice, Bob, Charlie, Dave, … — каждый новый элемент больше предыдущего и уходит только вправо, и дерево из 10 000 контактов превращается в цепочку высотой 10 000. Поиск деградирует до O(n) — не лучше неотсортированного массива. Чтобы дерево не вырождалось, придумали самобалансирующиеся деревья (AVL, red-black): они при каждой вставке и удалении перестраивают форму и держат высоту на уровне log n, гарантируя O(log n) даже на «алфавитном» порядке. Их устройство — отдельная тема; здесь достаточно знать, что гарантированный баланс существует и за него платят усложнением вставки/удаления.
Реализация
Ruby-реализация без балансировки — достаточна для понимания базовых операций. Узел хранит значение и ссылки на левого и правого ребёнка (nil, если ребёнка нет); дерево — это ссылка на корень.
class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
end
class BinarySearchTree
def initialize
@root = nil
end
def search(value)
return nil unless @root
current_node = @root
while current_node && current_node.value != value do
if value > current_node.value
current_node = current_node.right
else
current_node = current_node.left
end
end
current_node
end
def add(value)
new_node = Node.new(value)
return @root = new_node unless @root
current_node = @root
while current_node.value != value do
bigger = value > current_node.value
next_node = bigger ? current_node.right : current_node.left
unless next_node
if bigger
current_node.right = new_node
else
current_node.left = new_node
end
return new_node
end
current_node = next_node
end
current_node
end
def delete(value)
@root = delete_node(@root, value)
end
def in_order(node = @root, &block)
return unless node
in_order(node.left, &block) # сначала всё меньшее
block.call(node.value) # потом сам узел
in_order(node.right, &block) # потом всё большее
end
private
def delete_node(node, value)
return nil unless node
if value < node.value
node.left = delete_node(node.left, value)
elsif value > node.value
node.right = delete_node(node.right, value)
else
return node.right unless node.left
return node.left unless node.right
successor = node.right
successor = successor.left while successor.left
node.value = successor.value
node.right = delete_node(node.right, successor.value)
end
node
end
endБалансировка спасает только при условии, что задача — действительно произвольный поиск по ключу. Когда от структуры нужно меньше — например, только быстро добавить элемент и каждый раз доставать максимум (или минимум), а не искать произвольное значение, — на этом ослабленном требовании выигрывает более простая структура: куча. Она даёт гарантированный O(log n) на вставку и извлечение крайнего элемента без всякой балансировки, потому что не пытается держать полный порядок — только выводить наибольший (или наименьший) наверх.
Другое направление возникает, когда узлов так много, что они не помещаются в оперативную память и лежат на диске. Диск читается крупными блоками — страницами, и одно такое чтение в тысячи раз дороже обращения к памяти, поэтому стоимость операции определяется уже не сравнениями, а числом обращений к диску, то есть высотой дерева. Узел BST хранит один ключ (значение, по которому идёт сравнение), значит один спуск — это столько чтений с диска, какова высота: при миллионе ключей это порядка 20 (log₂ 10⁶ ≈ 20). B-дерево бьёт по этому числу напрямую: один узел занимает целую страницу и хранит сразу много ключей, поэтому дерево получается низким — глубиной обычно в несколько уровней (часто 3–4), а значит в несколько чтений с диска.
Sources
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (BST invariant, search/insert/delete, высота и сложность).
← Бинарное дерево | далее: B-дерево · Skip List →