Сигнал задачи
Когда применять
Для большого числа запросов о предках в статическом дереве или для словаря, где высота дерева поиска должна оставаться логарифмической после обновлений.
Разбор механики
Сбалансированные деревья поиска: зачем нужны повороты
Обычный BST ускоряет операции только пока его высота мала. Балансирующее правило не меняет порядок ключей, а ограничивает высоту после вставок и удалений, поэтому путь поиска остаётся логарифмическим.
Инвариант
В AVL для каждой вершины разность высот левого и правого поддеревьев принадлежит {-1, 0, 1}. В красно-чёрном дереве корень и фиктивные листья чёрные, у красной вершины нет красного ребёнка, а все пути к листьям содержат одинаковое число чёрных вершин.
Как работает
- Левый или правый поворот локально меняет связи трёх поддеревьев, сохраняет симметричный порядок BST и уменьшает перекос. AVL выбирает одинарный или двойной поворот по направлению тяжёлых рёбер.
- После вставки AVL обновляет высоты на пути к корню и чинит первый нарушенный баланс; удаление может потребовать восстановления выше по нескольким уровням.
- Красно-чёрное дерево допускает больший разброс высот, но восстанавливает цветовые правила перекрашиваниями и поворотами. Эти инварианты гарантируют высоту O(log n), не требуя идеальной симметрии.
- C++ std::set и std::map предоставляют упорядоченный обход и O(log n) для основных операций. Стандарт гарантирует контракт сложности, но не требует конкретно красно-чёрную реализацию. Python dict хранит порядок вставки, а не сортировку ключей; стандартного ordered set/map с логарифмическими обновлениями в Python нет.
Когда выбирать
- Нужен упорядоченный set/map, lower_bound, predecessor/successor или стабильная худшая граница O(log n) после обновлений — выбирайте сбалансированное дерево или библиотечный контейнер с таким контрактом.
- Если порядок не нужен, хеш-таблица обычно проще и даёт ожидаемое O(1). Сортированный Python list с bisect ускоряет поиск до O(log n), но вставка остаётся O(n) из-за сдвига.
Разбор механики
LCA через двоичные подъёмы
Для каждой вершины заранее хранятся прыжки к предкам на 1, 2, 4, 8 и далее рёбер. Любую высоту подъёма можно собрать из степеней двойки, как число из установленных битов.
Инвариант
up[j][v] — предок вершины v на расстоянии 2^j, а depth[v] — расстояние от выбранного корня. Для корня в таблице используется согласованный sentinel, обычно сам корень.
Как работает
- DFS или BFS от корня задаёт depth и непосредственного родителя up[0][v]. Затем up[j][v] вычисляется как up[j - 1][up[j - 1][v]].
- Перед поиском LCA более глубокую вершину поднимают на разность глубин, проверяя биты этой разности.
- Если вершины не совпали, степени двойки перебирают от большой к малой и одновременно поднимают обе вершины там, где их 2^j-предки различаются. После цикла их непосредственный родитель и есть LCA.
- Подготовка занимает O(n log n) времени и памяти, один запрос — O(log n). Таблица относится к выбранному корню и статической структуре дерева; после изменения рёбер её нужно перестроить.
Когда выбирать
- Используйте binary lifting для большого числа запросов LCA или подъёма на k уровней в статическом дереве.
- Для одного или нескольких запросов простой подъём по родителям может быть достаточен; для динамического леса нужна другая структура и явно иной контракт.
Референсная реализация
Обе версии выражают один контракт и запускаются в автоматической проверке проекта.
C++17: подготовка и запросы LCA
#include <iostream>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
class BinaryLifting {
public:
BinaryLifting(const std::vector<std::vector<int>>& graph, int root)
: size_(static_cast<int>(graph.size())) {
if (size_ == 0 || root < 0 || root >= size_) {
throw std::invalid_argument("tree and root must be valid");
}
long long degree_sum = 0;
for (const auto& neighbors : graph) {
degree_sum += static_cast<long long>(neighbors.size());
}
if (degree_sum != 2LL * (size_ - 1)) {
throw std::invalid_argument("graph must contain n - 1 undirected edges");
}
levels_ = 1;
while ((1LL << levels_) <= size_) {
++levels_;
}
depth_.assign(size_, -1);
up_.assign(levels_, std::vector<int>(size_, root));
std::queue<int> queue;
queue.push(root);
depth_[root] = 0;
up_[0][root] = root;
while (!queue.empty()) {
const int vertex = queue.front();
queue.pop();
for (const int next : graph[vertex]) {
check_vertex(next);
if (next == up_[0][vertex]) {
continue;
}
if (depth_[next] != -1) {
throw std::invalid_argument("graph must be a tree");
}
depth_[next] = depth_[vertex] + 1;
up_[0][next] = vertex;
queue.push(next);
}
}
for (const int depth : depth_) {
if (depth == -1) {
throw std::invalid_argument("tree must be connected");
}
}
for (int level = 1; level < levels_; ++level) {
for (int vertex = 0; vertex < size_; ++vertex) {
up_[level][vertex] = up_[level - 1][up_[level - 1][vertex]];
}
}
}
int kth_ancestor(int vertex, int distance) const {
check_vertex(vertex);
if (distance < 0 || distance > depth_[vertex]) {
throw std::out_of_range("ancestor is above the root");
}
for (int level = 0; distance > 0; ++level, distance >>= 1) {
if (distance & 1) {
vertex = up_[level][vertex];
}
}
return vertex;
}
int lca(int first, int second) const {
check_vertex(first);
check_vertex(second);
if (depth_[first] < depth_[second]) {
std::swap(first, second);
}
first = kth_ancestor(first, depth_[first] - depth_[second]);
if (first == second) {
return first;
}
for (int level = levels_ - 1; level >= 0; --level) {
if (up_[level][first] != up_[level][second]) {
first = up_[level][first];
second = up_[level][second];
}
}
return up_[0][first];
}
private:
int size_ = 0;
int levels_ = 0;
std::vector<int> depth_;
std::vector<std::vector<int>> up_;
void check_vertex(int vertex) const {
if (vertex < 0 || vertex >= size_) {
throw std::out_of_range("vertex is outside the tree");
}
}
};
int main() {
std::vector<std::vector<int>> tree(9);
for (const auto [first, second] : std::vector<std::pair<int, int>>{
{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {6, 7}, {7, 8}}) {
tree[first].push_back(second);
tree[second].push_back(first);
}
BinaryLifting lifting(tree, 0);
std::cout << lifting.lca(3, 4) << '\n';
std::cout << lifting.lca(3, 8) << '\n';
std::cout << lifting.kth_ancestor(8, 4) << '\n';
std::cout << lifting.lca(6, 8) << '\n';
}Python 3: тот же двоичный подъём
from collections import deque
class BinaryLifting:
def __init__(self, graph: list[list[int]], root: int) -> None:
self._size = len(graph)
if self._size == 0 or not 0 <= root < self._size:
raise ValueError("tree and root must be valid")
if sum(map(len, graph)) != 2 * (self._size - 1):
raise ValueError("graph must contain n - 1 undirected edges")
self._levels = max(1, self._size.bit_length())
self._depth = [-1] * self._size
self._up = [[root] * self._size for _ in range(self._levels)]
self._depth[root] = 0
self._up[0][root] = root
queue = deque([root])
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
self._check_vertex(neighbor)
if neighbor == self._up[0][vertex]:
continue
if self._depth[neighbor] != -1:
raise ValueError("graph must be a tree")
self._depth[neighbor] = self._depth[vertex] + 1
self._up[0][neighbor] = vertex
queue.append(neighbor)
if any(depth == -1 for depth in self._depth):
raise ValueError("tree must be connected")
for level in range(1, self._levels):
for vertex in range(self._size):
middle = self._up[level - 1][vertex]
self._up[level][vertex] = self._up[level - 1][middle]
def kth_ancestor(self, vertex: int, distance: int) -> int:
self._check_vertex(vertex)
if not 0 <= distance <= self._depth[vertex]:
raise IndexError("ancestor is above the root")
level = 0
while distance > 0:
if distance & 1:
vertex = self._up[level][vertex]
distance >>= 1
level += 1
return vertex
def lca(self, first: int, second: int) -> int:
self._check_vertex(first)
self._check_vertex(second)
if self._depth[first] < self._depth[second]:
first, second = second, first
first = self.kth_ancestor(first, self._depth[first] - self._depth[second])
if first == second:
return first
for level in range(self._levels - 1, -1, -1):
if self._up[level][first] != self._up[level][second]:
first = self._up[level][first]
second = self._up[level][second]
return self._up[0][first]
def _check_vertex(self, vertex: int) -> None:
if not 0 <= vertex < self._size:
raise IndexError("vertex is outside the tree")
tree = [[] for _ in range(9)]
for first, second in [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (6, 7), (7, 8)]:
tree[first].append(second)
tree[second].append(first)
lifting = BinaryLifting(tree, 0)
print(lifting.lca(3, 4))
print(lifting.lca(3, 8))
print(lifting.kth_ancestor(8, 4))
print(lifting.lca(6, 8))Как выбрать подход
- Binary lifting удобен для LCA и подъёма вершины на k уровней: таблица предков строится один раз для статического дерева.
- Euler tour с RMQ сводит LCA к минимуму глубины на отрезке; вариант RMQ определяет цену подготовки и запроса.
- AVL строже ограничивает разность высот и обычно даёт более низкое дерево поиска, но может делать больше балансирующих действий при обновлениях.
- Красно-чёрное дерево поддерживает более слабый цветовой инвариант; поиск, вставка и удаление остаются O(log n), что подходит для общего упорядоченного словаря.
Сложность
- LCA с binary lifting: подготовка O(n log n), запрос и подъём O(log n), память O(n log n).
- Euler tour занимает O(n); со sparse table подготовка RMQ O(n log n), запрос LCA O(1), память O(n log n).
- AVL: поиск, вставка и удаление O(log n), память O(n); высоты обновляются вдоль пути к корню.
- Красно-чёрное дерево: поиск, вставка и удаление O(log n), память O(n).
Границы и ошибки
- Таблица LCA неверна без согласованных глубин, корня и обработки разных компонент леса.
- После поворота AVL нужно обновлять высоты снизу вверх, включая обе изменившиеся вершины.
- Удаление в красно-чёрном дереве требует восстановить цветовые инварианты; одной перестановки указателей недостаточно.
- Политика равных ключей и компаратор должны задавать строгий порядок, иначе поиск и балансировка расходятся.