Ответ
Сложность операций с деревьями кардинально зависит от того, сбалансировано дерево или нет.
| Сводная таблица сложностей: | Операция | Сбалансированное дерево (AVL, Красно-черное) | Несбалансированное дерево (вырожденное в список) |
|---|---|---|---|
| Поиск | O(log n) | O(n) | |
| Вставка | O(log n) | O(n) | |
| Удаление | O(log n) | O(n) | |
| Обход (in-order, pre-order, post-order) | O(n) (посещение всех узлов) | O(n) |
Почему такая разница? В сбалансированном дереве высота ~log₂(n), и на каждом шаге алгоритм отбрасывает половину поддерева. В вырожденном дереве (цепочке узлов) высота равна n.
Пример поиска в бинарном дереве поиска (BST) на PHP:
class BinarySearchTree {
public $val;
public ?BinarySearchTree $left = null;
public ?BinarySearchTree $right = null;
public function search(int $target): ?BinarySearchTree {
$current = $this;
while ($current !== null) {
if ($target === $current->val) {
return $current; // Найден
}
// Спускаемся в левое или правое поддерево
$current = $target < $current->val ? $current->left : $current->right;
}
return null; // Не найден
}
}
// В сбалансированном дереве цикл выполнится не более log n раз.B-деревья и B+ деревья, используемые в файловых системах и СУБД (индексы), также имеют сложность O(log n) для операций поиска/вставки, но с очень низким коэффициентом (широкое ветвление), что минимизирует обращения к диску.