Daily bit(e) C++. Алгоритмы обхода дерева
Daily bit(e) C++ 18. Рассмотрим алгоритмы, которые стоит знать: обход дерева
Хотя стандартная библиотека C++ предлагает широкий спектр алгоритмов, один тип, который, к сожалению, до сих пор полностью отсутствует, – это алгоритмы для работы с графами (и, следовательно, с деревьями). Хотя над этим ведется работа (см. P1709), пока единственный вариант – воспроизводить стандартные решения с нуля, когда алгоритмы для работы с графами встречаются на собеседованиях.
Введение
Прежде чем мы начнем обзор алгоритмов обхода дерева, стоит поговорить о структуре данных «дерево».
Наиболее простой подход к представлению дерева – использование одной структуры:
#include <memory>
#include <string>
template <typename T>
struct TreeNode
{
T value = T{};
std::unique_ptr<TreeNode> left;
std::unique_ptr<TreeNode> right;
};
auto root = std::make_unique<TreeNode<std::string>>("root node", nullptr, nullptr);
// root->value == "root node"
root->left = std::make_unique<TreeNode<std::string>>("left node", nullptr, nullptr);
// root->left->value == "left node"
root->right = std::make_unique<TreeNode<std::string>>("right node", nullptr, nullptr);
// root->right->value == "right node"
Этот подход прост и предлагает удобный интерфейс. Например, для объединения деревьев достаточно вызвать std::swap для исходного и целевого std::unique_ptr.
Однако у него есть фатальный недостаток. Поскольку наша структура данных рекурсивна, и мы полагаемся на сгенерированные деструкторы, мы получаем рекурсивное уничтожение. Достаточно глубокое дерево может быстро исчерпать стек во время своего уничтожения, что приводит к повреждению памяти или сбою.
Мы можем смягчить эту проблему, отделив представление структуры дерева от управления памятью:
#include <memory>
#include <vector>
#include <string>
template <typename T>
struct Tree
{
struct Node
{
T value = T{};
Node* left = nullptr;
Node* right = nullptr;
};
Node* add(auto&& ... args)
{
storage_.push_back(std::make_unique<Node>(
std::forward<decltype(args)>(args)...));
return storage_.back().get();
}
Node* root;
private:
std::vector<std::unique_ptr<Node>> storage_;
};
Tree<std::string> tree;
tree.root = tree.add("root node");
// tree.root->value == "root node"
tree.root->left = tree.add("left node");
// tree.root->left->value == "left node"
tree.root->right = tree.add("right node");
// tree.root->right->value == "right node"
Это полностью исключает рекурсивное уничтожение, однако за это приходится платить. Хотя мы по-прежнему можем легко объединять элементы внутри дерева, объединение между деревьями становится громоздким.
Поскольку мы говорим о C++, стоит отметить, что ни один из вышеописанных подходов не является производительным. Самая большая проблема заключается в том, что мы аллоцируем каждый узел отдельно, а это означает, что они могут быть расположены далеко друг от друга, в худшем случае каждый узел будет отображаться на разную кэш-линию.
Один из способов решения этой проблемы – хранить узлы «на месте», при этом информация о том, какой узел является чьим дочерним элементом, хранится отдельно:
#include <memory>
#include <vector>
#include <optional>
#include <string>
#include <iostream>
template <typename T>
struct Tree
{
struct Children
{
std::optional<size_t> left = std::nullopt;
std::optional<size_t> right = std::nullopt;
};
std::vector<T> data;
std::vector<Children> children;
size_t add(auto&&... args)
{
data.emplace_back(std::forward<decltype(args)>(args)...);
children.push_back(Children{});
return data.size()-1;
}
size_t add_as_left_child(size_t idx, auto&&... args)
{
size_t cid = add(std::forward<decltype(args)>(args)...);
children[idx].left = cid;
return cid;
}
size_t add_as_right_child(size_t idx, auto&&... args)
{
size_t cid = add(std::forward<decltype(args)>(args)...);
children[idx].right = cid;
return cid;
}
};
Tree<std::string> tree;
auto root = tree.add("root node");
// tree.data[root] == "root node"
auto left = tree.add_as_left_child(root, "left node");
// tree.data[left] == "left node", tree.children[root].left == left
auto right = tree.add_as_right_child(root, "right node");
// tree.data[right] == "right node", tree.children[root].right == right
Обратите внимание, что мы снова добавляем сложность. Это связано с тем, что у нас больше нет стабильных адресов, и добавление каждого узла может сделать недействительными местоположения предыдущих узлов (из-за того, как std::vector работает с памятью). Поэтому нам необходимо полагаться на индексы, что, с другой стороны, делает сериализацию тривиальной, поскольку индексы остаются стабильными.
Обход деревьев
Существует четыре типа обхода деревьев, которые стоит запомнить, поскольку они регулярно встречаются на собеседованиях по программированию. Мы рассмотрим каждый из них и посмотрим на некоторые типичные применения.
Прямой (pre-order) обход
При прямом обходе каждый узел посещается до своих дочерних узлов.
// прямой обход
void pre_order(Node *node, const std::function<void(Node*)>& visitor)
{
if (node == nullptr)
return;
visitor(node);
pre_order(node->left, visitor);
pre_order(node->right, visitor);
}
Из-за такого порядка прямой обход обычно используется для сериализации и десериализации.
// сериализация с помощью прямого обхода
void serialize(Node *node, std::ostream& s)
{
if (node == nullptr)
{
s << 0 << " ";
return;
}
s << node->value << " ";
serialize(node->left, s);
serialize(node->right, s);
}
// десериализация с помощью прямого обхода
Tree<int>::Node *deserialize_single(Tree<int>& tree, std::istream& s)
{
int value = 0;
if (!(s >> value) || value <= 0)
return nullptr;
return tree.add(value);
}
Tree<int>::Node *deserialize(Tree<int>& tree, std::istream& s)
{
auto node = deserialize_single(tree, s);
if (node == nullptr)
return node;
node->left = deserialize(tree, s);
node->right = deserialize(tree, s);
return node;
}
Tree<int> tree;
// десериализация
tree.root = deserialize(tree, std::cin);
// сериализация
serialize(tree.root, std::cout);
std::cout << "\n";
Как уже упоминалось, рекурсивный подход может быть проблематичным из-за исчерпания стека. Поэтому давайте также рассмотрим альтернативную реализацию с использованием std::stack.
void pre_order_stack(Node* root, const std::function<void(Node*)>& visitor)
{
std::stack<Node*> stack;
stack.push(root);
while (!stack.empty())
{
Node *curr = stack.top();
stack.pop();
visitor(curr);
// При этом подходе мы посещаем "нулевые" узлы, что может быть полезно.
// В качестве альтернативы мы можем перенести условие в операцию добавления:
// if (curr->right != nullptr) stack.push(curr->right);
if (curr == nullptr)
continue;
// Если мы хотим поддерживать такой же порядок, как при рекурсивном обходе,
// то мы должны добавлять потомков в обратном порядке.
stack.push(curr->right);
stack.push(curr->left);
}
}
Обратный (post-order) обход
При обратном обходе каждый узел посещается после своих дочерних узлов.
// обратный обход
void post_order(Node *node, const std::function<void(Node*)>& visitor)
{
if (node == nullptr)
return;
post_order(node->left, visitor);
post_order(node->right, visitor);
visitor(node);
}
Благодаря такому порядку, обратный обход можно использовать в выражениях для деревьев, где родительское выражение может быть вычислено только в том случае, если уже были вычислены выражения обоих его потомков.
struct Eventual
{
std::optional<int> result;
std::function<int(const Eventual& l, const Eventual& r)> op;
};
Tree<Eventual> tree;
auto plus = [](const Eventual& l, const Eventual& r) {
return *l.result + *r.result;
};
auto minus = [](const Eventual& l, const Eventual& r) {
return *l.result - *r.result;
};
auto times = [](const Eventual& l, const Eventual& r) {
return *l.result * *r.result;
};
// закодируем(4-2)*(2+1)
auto root = tree.root = tree.add(Eventual{std::nullopt, times});
auto left = root->left = tree.add(Eventual{std::nullopt, minus});
auto right = root->right = tree.add(Eventual{std::nullopt, plus});
left->left = tree.add(Eventual{4, {}});
left->right = tree.add(Eventual{2, {}});
right->left = tree.add(Eventual{2, {}});
right->right = tree.add(Eventual{1, {}});
post_order(tree.root, [](Node* node)
{
// если этот узел уже имеет результирующее значение, ничего не делаем
if (node->value.result)
return;
// если это операция, вычисление в обратном порядке гарантирует,
// что node->left->value и node->right->value уже имеют результирующие значения
node->value.result = node->value.op(node->left->value, node->right->value);
});
// *tree.root->value.result == 6
Для нерекурсивного подхода мы могли бы пройти по всем узлам в порядке прямого обхода, запоминая каждый (например, снова используя std::stack), а затем пройтись по узлам в обратном порядке. Однако мы можем сделать лучше:
void post_order_nonrecursive(Node *root,
const std::function<void(Node*)>& visitor)
{
std::stack<Node*> s;
Node *current = root;
while (true)
{
// раскрываем левого потомка, но запоминаем текущий узел и правого потомка
if (current != nullptr)
{
if (current->right != nullptr)
s.push(current->right);
s.push(current);
current = current->left;
continue;
}
// current == nullptr
if (s.empty())
return;
current = s.top();
s.pop();
// Если у нас есть запомненный правый потомок,
// он должен быть на вершине стека.
if (current->right && !s.empty() && current->right == s.top())
{
// если это так, мы сначала должны посетить его (и его потомков)
s.pop();
s.push(current);
current = current->right;
}
else
{
visitor(current);
current = nullptr;
}
}
}
Центрированный (in-order) обход
При центрированном обходе мы посещаем каждый узел между посещениями его левого и правого потомков.
// центрированный обход
void in_order(Node* node, const std::function<void(Node*)>& visitor)
{
if (node == nullptr)
return;
in_order(node->left, visitor);
visitor(node);
in_order(node->right, visitor);
}
Типичный сценарий использования – обход деревьев с определенным порядком, при котором этот порядок должен сохраняться на протяжении всего обхода.
Например, в следующем примере мы создаем простое отсортированное бинарное дерево (для каждого узла все узлы в левом поддереве имеют меньшие или равные значения, а все узлы в правом поддереве – большие значения), а затем обходим его, чтобы получить отсортированный список чисел:
void add_sorted(Tree<int64_t>& tree, Node* node, int64_t value)
{
if (value <= node->value)
{
if (node->left == nullptr)
node->left = tree.add(value);
else
add_sorted(tree, node->left, value);
}
else
{
if (node->right == nullptr)
node->right = tree.add(value);
else
add_sorted(tree, node->right, value);
}
}
Tree<int64_t> tree;
// Генерируем сортированное бинарное дерево из 10 узлов
std::mt19937 gen(0); // для другого результата замените начальное значение
std::uniform_int_distribution<> dist(0,1000);
tree.root = tree.add(dist(gen));
for (int i = 0; i < 9; i++)
{
add_sorted(tree, tree.root, dist(gen));
}
// центрированный обход напечатает значения в отсортированном порядке
in_order(tree.root, [](Node* node) {
std::cout << node->value << " ";
});
std::cout << "\n";
// stdlibc++: 424 545 549 593 603 624 715 845 848 858
// libc++: 9 192 359 559 629 684 707 723 763 835
Нерекурсивный подход аналогичен обратному обходу, но мы удаляем сложность запоминания правого потомка.
void in_order_nonrecursive(Node *root,
const std::function<void(Node*)>& visitor)
{
std::stack<Node*> s;
Node *current = root;
while (current != nullptr || !s.empty())
{
// раскрываем левого потомка
while (current != nullptr)
{
s.push(current);
current = current->left;
}
// Теперь, двигаясь обратно по левому пути,
// посещаем каждый узел, а затем раскрываем правого потомка.
// Это работает, потому что левый потомок уже был посещен,
// когда мы двигались вверх по пути.
current = s.top();
s.pop();
visitor(current);
current = current->right;
}
}
Ранжированный (ranked-order) обход
Наконец, стоит упомянуть ранжированный обход или обход по уровням, при котором мы обходим узлы в порядке их расстояния от корневого узла (и обычно слева направо).
В то время как все предыдущие обходы основывались на поиске в глубину, этот основан на алгоритме поиска в ширину.
void rank_order(Node* root, const std::function<void(Node*)>& visitor)
{
std::queue<Node*> q;
if (root != nullptr)
q.push(root);
while (!q.empty())
{
Node* current = q.front();
q.pop();
if (current == nullptr)
continue;
visitor(current);
q.push(current->left);
q.push(current->right);
}
}
Ранжированный обход в обычно встречается в более сложных задачах. По умолчанию его можно использовать для поиска ближайшего к корню узла, удовлетворяющего определенным критериям, или для вычисления расстояний от узлов до корня.
Вот пример вычисления максимального значения на каждом уровне дерева:
std::vector<int> max_at_level(Node* root)
{
std::vector<int> result;
std::queue<std::pair<Node*,size_t>> q;
if (root != nullptr)
q.push({root,0});
while (!q.empty())
{
auto [node,rank] = q.front();
q.pop();
if (result.size() <= rank)
result.push_back(node->value);
else
result[rank] = std::max(result[rank], node->value);
if (node->left != nullptr)
q.push({node->left,rank+1});
if (node->right != nullptr)
q.push({node->right, rank+1});
}
return result;
}
Сложность
Все рассмотренные алгоритмы являются обходами дерева, поэтому они по своей природе имеют временную сложность O(n). Однако стоит упомянуть и пространственную сложность.
Для обходов в глубину (pre-order, post-order, in-order) пространственная сложность определяется максимальной глубиной дерева.
Для обхода в ширину в порядке ранжирования пространственная сложность определяется максимальной шириной дерева.