🌳 Структури от тип Дърво (Tree Structures)
Дървото е свързан ациклен граф (граф без цикли). То е една от най-важните структури в информатиката заради своята йерархична природа и специалните си свойства. Дървета се появяват навсякъде - от файлови системи и организационни структури до сложни алгоритмични задачи.
Основни свойства на дървото: - Дърво с \(n\) върха има точно \(n-1\) ребра - Между всеки два върха има точно един прост път - Премахването на произволно ребро разделя дървото на две компоненти - Добавянето на произволно ребро създава точно един цикъл
1. Основни понятия
- Корен (Root): Специален връх, от който започва йерархията. При некоренирани дървета можем да изберем произволен връх за корен.
- Родител (Parent): Директният предшественик на даден връх в йерархията.
- Дете (Child): Директен наследник на даден връх.
- Листо (Leaf): Връх без деца. В некоренирано дърво това е връх със степен 1.
- Поддърво (Subtree): Дърво, образувано от даден връх и всичките му наследници.
- Дълбочина (Depth): Разстоянието от корена до даден връх.
- Височина (Height): Максималното разстояние от корена до листо. Alternatively, височината на връх е максималното разстояние до листо в неговото поддърво.
- Ниво (Level): Множеството от всички върхове с еднаква дълбочина.
- Двоично дърво (Binary Tree): Всеки връх има най-много 2 деца (ляво и дясно).
- Пълно двоично дърво: Всички нива са напълно запълнени, освен евентуално последното.
1.1. Базова структура в паметта
// Представяне чрез списъци на съседство
vector<int> adj[MAXN];
// Представяне с родител и деца (коренирано дърво)
int parent[MAXN];
vector<int> children[MAXN];
// Двоично дърво с указатели
struct Node {
int value;
Node *left, *right;
Node(int val) : value(val), left(nullptr), right(nullptr) {}
};
2. Обхождане на дървета
Обхождането на дървета е фундаментална операция. Има няколко класически начина:
2.1. Обхождане в дълбочина (DFS-based)
- Pre-order (Корен → Ляво → Дясно): Посещаваме корена преди децата му.
- Използва се за: копиране на дървото, създаване на префиксна нотация
void preorder(Node* node) {
if (!node) return;
process(node->value); // Обработваме корена
preorder(node->left); // Обхождаме лявото поддърво
preorder(node->right); // Обхождаме дясното поддърво
}
- In-order (Ляво → Корен → Дясно): Посещаваме корена между двете поддървета.
- Използва се за: BST обхождане дава сортирана редица
void inorder(Node* node) {
if (!node) return;
inorder(node->left); // Обхождаме лявото поддърво
process(node->value); // Обработваме корена
inorder(node->right); // Обхождаме дясното поддърво
}
- Post-order (Ляво → Дясно → Корен): Посещаваме корена след децата му.
- Използва се за: изтриване на дървото, изчисляване на постфиксни изрази, DP на дървета
void postorder(Node* node) {
if (!node) return;
postorder(node->left); // Обхождаме лявото поддърво
postorder(node->right); // Обхождаме дясното поддърво
process(node->value); // Обработваме корена
}
2.2. Обхождане в ширина (BFS - Level Order)
Обхождаме дървото ниво по ниво, отляво надясно:
void levelOrder(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
process(current->value);
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
2.3. Обхождане на общо дърво (не задължително двоично)
void dfs(int u, int parent = -1) {
// Pre-order обработка
process(u);
for (int v : adj[u]) {
if (v != parent) {
dfs(v, u);
}
}
// Post-order обработка
postprocess(u);
}
3. Най-близък общ прародител (LCA)
LCA (Lowest Common Ancestor) на върховете \(u\) и \(v\) е най-дълбокият връх, който е прародител и на двата. Това е една от най-важните операции върху дървета.
Приложения на LCA: - Намиране на разстояние между два върха: \(dist(u, v) = depth[u] + depth[v] - 2 \times depth[LCA(u, v)]\) - Проверка дали един връх е в пътя между други два - Range queries върху пътища в дървото
3.1. Наивен подход
Вдигаме двата върха нагоре докато не се срещнат. Сложност: \(O(h)\) където \(h\) е височината.
int lca_naive(int u, int v) {
// Първо ги правим на еднаква дълбочина
while (depth[u] > depth[v]) u = parent[u];
while (depth[v] > depth[u]) v = parent[v];
// После ги вдигаме едновременно
while (u != v) {
u = parent[u];
v = parent[v];
}
return u;
}
3.2. Двоично повдигане (Binary Lifting)
Позволява намиране на LCA за \(O(\log N)\) след \(O(N \log N)\) препроцесинг. Това е стандартният и най-популярен метод.
Идея: Пазим за всеки връх неговия \(2^i\)-ти прародител за \(i = 0, 1, 2, \ldots, \log N\).
const int MAXN = 100005;
const int LOGN = 20; // log2(100000) ≈ 17
int up[MAXN][LOGN]; // up[u][i] = 2^i-тият прародител на u
int depth[MAXN];
vector<int> adj[MAXN];
void dfs(int u, int p = 0) {
up[u][0] = p; // Директният родител
// Изчисляваме 2^i-тите прародители
for (int i = 1; i < LOGN; i++) {
up[u][i] = up[up[u][i-1]][i-1];
}
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
}
// Връща k-тия прародител на u
int kth_ancestor(int u, int k) {
for (int i = 0; i < LOGN; i++) {
if (k & (1 << i)) {
u = up[u][i];
}
}
return u;
}
bool is_ancestor(int u, int v) {
// Проверяваме дали u е прародител на v
return kth_ancestor(v, depth[v] - depth[u]) == u;
}
int lca(int u, int v) {
// Уверяваме се че u е по-дълбокият
if (depth[u] < depth[v]) swap(u, v);
// Вдигаме u до нивото на v
u = kth_ancestor(u, depth[u] - depth[v]);
if (u == v) return u;
// Двоично търсене на LCA
for (int i = LOGN - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0]; // Родителят на текущата позиция
}
// Инициализация
void init(int root, int n) {
depth[root] = 0;
dfs(root);
}
3.3. Други подходи за LCA
Eulerian Tour + RMQ: Сложност \(O(N)\) preprocessing, \(O(1)\) per query с Sparse Table.
Tarjan's Offline LCA: Полезен когато всички заявки са известни предварително.
4. Диаметър на дърво
Диаметърът е най-дългият път между два върха в дървото. Това е важна характеристика на дървото с много приложения.
4.1. Алгоритъм с две DFS
Най-ефективният начин за намиране на диаметър:
int farthest_node;
int max_dist;
void dfs(int u, int parent, int dist) {
if (dist > max_dist) {
max_dist = dist;
farthest_node = u;
}
for (int v : adj[u]) {
if (v != parent) {
dfs(v, u, dist + 1);
}
}
}
int findDiameter(int n) {
// Стъпка 1: Намираме най-далечен връх от произволен връх (например 1)
max_dist = 0;
dfs(1, -1, 0);
int endpoint1 = farthest_node;
// Стъпка 2: Намираме най-далечен връх от endpoint1
max_dist = 0;
dfs(endpoint1, -1, 0);
// max_dist сега съдържа диаметъра
return max_dist;
}
Обяснение защо работи: - След първия DFS намираме един от краищата на диаметъра - Втори DFS от това крайниче ни дава другото крайниче и дължината
4.2. Диаметър с DP (един DFS)
Алтернативен подход използвайки dynamic programming:
int diameter = 0;
int dfs_diameter(int u, int parent) {
int max1 = 0, max2 = 0; // Две най-дълги пътя надолу
for (int v : adj[u]) {
if (v != parent) {
int h = dfs_diameter(v, u);
if (h > max1) {
max2 = max1;
max1 = h;
} else if (h > max2) {
max2 = h;
}
}
}
// Диаметърът през u е max1 + max2
diameter = max(diameter, max1 + max2);
// Връщаме най-дългия път надолу от u
return max1 + 1;
}
4.3. Намиране на центъра на дървото
Центърът е върхът/върховете, които минимизират максималното разстояние до всички други върхове. Центърът винаги лежи на диаметъра.
vector<int> findCenter(int n) {
// Намираме диаметъра и двата му края
// ... (код от по-горе)
int mid = max_dist / 2;
// Вървим mid стъпки от едното крайниче
// Това е/са центърът/центровете
}
5. Специализирани дървета и техники
5.1. Двоично дърво за търсене (BST)
BST поддържа елементите в сортиран ред. За всеки връх: - Всички елементи в лявото поддърво са по-малки - Всички елементи в дясното поддърво са по-големи
struct BST {
int value;
BST *left, *right;
BST(int val) : value(val), left(nullptr), right(nullptr) {}
};
BST* insert(BST* root, int val) {
if (!root) return new BST(val);
if (val < root->value) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
bool search(BST* root, int val) {
if (!root) return false;
if (root->value == val) return true;
if (val < root->value) return search(root->left, val);
return search(root->right, val);
}
Забележка: Обикновено BST може да се дебалансира. За балансирани BST вижте AVL дървета, Red-Black дървета или използвайте set в C++.
5.2. Trie (Prefix Tree)
Ефективна структура за работа с низове:
struct TrieNode {
map<char, TrieNode*> children;
bool isEnd = false;
};
class Trie {
TrieNode* root;
public:
Trie() { root = new TrieNode(); }
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
if (!curr->children[c]) {
curr->children[c] = new TrieNode();
}
curr = curr->children[c];
}
curr->isEnd = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
if (!curr->children[c]) return false;
curr = curr->children[c];
}
return curr->isEnd;
}
};
5.3. Segment Tree и Fenwick Tree
Тези дървета се използват за range queries и updates. Детайлна информация в Topic 34.
5.4. Heavy-Light Decomposition
Разделя дървото на "тежки" и "леки" пътища, позволявайки ефективни заявки върху пътища. Сложност: \(O(\log^2 N)\) per query.
5.5. Centroid Decomposition
Рекурсивно разделяне на дървото чрез центроид (връх, чието премахване прави всички компоненти с размер ≤ n/2). Използва се за сложни задачи с пътища в дървото.
6. Dynamic Programming на дървета
DP на дървета е мощна техника. Обикновено използваме post-order обхождане:
6.1. Пример: Максимална независима множество
Намираме максимален брой върхове такива, че никои два не са свързани с ребро.
int dp[MAXN][2]; // dp[u][0] = не включваме u, dp[u][1] = включваме u
void tree_dp(int u, int parent) {
dp[u][0] = 0;
dp[u][1] = 1; // Стойността на u
for (int v : adj[u]) {
if (v != parent) {
tree_dp(v, u);
// Ако не вземаме u, можем да вземем или не v
dp[u][0] += max(dp[v][0], dp[v][1]);
// Ако вземаме u, НЕ можем да вземем v
dp[u][1] += dp[v][0];
}
}
}
6.2. Rerooting technique
Понякога искаме DP резултати за всеки възможен корен. Използваме rerooting:
int down[MAXN]; // DP надолу (към листата)
int up[MAXN]; // DP нагоре (към корена)
// Първо изчисляваме down[] с обикновен DFS
void dfs_down(int u, int parent) {
down[u] = 0;
for (int v : adj[u]) {
if (v != parent) {
dfs_down(v, u);
down[u] += down[v] + 1; // Пример
}
}
}
// После изчисляваме up[] с rerooting
void dfs_up(int u, int parent) {
for (int v : adj[u]) {
if (v != parent) {
// up[v] се изчислява от up[u] и down на другите деца
up[v] = up[u] + down[u] - down[v] - 1;
dfs_up(v, u);
}
}
}
7. Euler Tour и други техники
7.1. Euler Tour на дървото
Преобразуваме дървото в масив, позволявайки използване на range structures:
int timer = 0;
int tin[MAXN], tout[MAXN];
int euler[2 * MAXN]; // Euler tour
void euler_tour(int u, int parent) {
tin[u] = timer;
euler[timer++] = u;
for (int v : adj[u]) {
if (v != parent) {
euler_tour(v, u);
}
}
tout[u] = timer;
euler[timer++] = u;
}
Сега поддървото на \(u\) съответства на интервал \([tin[u], tout[u]]\).
7.2. Flattening на дървото
Подобно на Euler tour, но по-просто - всяко поддърво е непрекъснат интервал:
int timer = 0;
int tin[MAXN], tout[MAXN];
void flatten(int u, int parent) {
tin[u] = timer++;
for (int v : adj[u]) {
if (v != parent) flatten(v, u);
}
tout[u] = timer - 1;
}
8. Задачи за упражнение
Основни задачи
- CSES Tree Diameter: Намиране на диаметъра - отлична за начало.
- CSES Subordinates: Преброяване на поддървета - базов tree DP.
- CSES Tree Distances I: Разстояния в дърво - комбинация от техники.
Средни задачи
- CSES Company Queries II: Намиране на LCA с binary lifting.
- Codeforces 191C: Fools and Roads - LCA + разлики върху дърво.
- CSES Path Queries: Заявки върху пътища - Euler tour + range структури.
- CSES Tree Distances II: Rerooting technique.
Напреднали задачи
- Codeforces 609E: Minimum Spanning Tree для Each Edge.
- CSES Distinct Colors: Heavy-Light Decomposition или друга напреднала техника.
- IOI 2011 Race: Centroid decomposition класическа задача.
9. Практически съвети
9.1. Често срещани грешки
- Забравяне на проверка за родител при DFS в некоренирано дърво
- Грешна инициализация на binary lifting масива
- Off-by-one грешки при изчисляване на дълбочина/височина
- Stack overflow при много дълбоки дървета - използвайте итеративен DFS или увеличете stack size
9.2. Оптимизации
- При binary lifting, не забравяйте че
up[0][i] = 0(или sentinel value) - За Euler tour, размерът на масива трябва да е
2*n - При rerooting, внимавайте с обновяването на стойности
- Използвайте
vector<int>вместоvector<vector<int>>за по-добра cache locality
9.3. Debugging съвети
- Визуализирайте малки дървета (5-7 върха)
- Проверете дали коренът е правилно обработен
- Принтирайте междинните стойности на DP
- Тествайте с линейно дърво (най-лош случай) и звезда (специален случай)
🏁 Заключение
Дърветата са фундаментална структура в състезателното програмиране и компютърните науки. Основните техники, които трябва да овладеете са:
Must-know техники: - Обхождания: DFS (pre/in/post-order) и BFS - LCA: Binary lifting е стандартът - Диаметър: Двойно DFS или DP - Tree DP: Post-order обхождане за изчисление на стойности
Advanced техники:
- Rerooting: За DP с всички възможни корени
- Euler Tour: Преобразува дърво в масив за range queries
- Heavy-Light Decomposition: За сложни заявки върху пътища
- Centroid Decomposition: За задачи с разстояния в дървото
Дърветата позволяват много операции да бъдат изпълнени за логаритмично време. Разбирането на LCA и динамичното програмиране върху дървета е критично за напреднали състезатели. Практикувайте редовно с различни типове задачи за да развиете интуиция за правилния подход!