Блог

Все операции с деревом вырезания ссылок описаны в предположении, что у нас уже есть узел, с которым мы хотим выполнить операцию, но как мне сохранить дерево, чтобы иметь возможность добраться до этого узла в первую очередь?

Я не могу просто сохранить корень абстрактного дерева, потому что деревья с вырезанными ссылками не поддерживают поиск потомков, поэтому большинство узлов в дереве будут потеряны.

У меня была идея хранить корни каждого сплошного дерева (splay tree) в векторе, но есть еще одна проблема: сплошные деревья постоянно меняют свою структуру, а это значит, что мне придется пересчитывать корни каждого дерева после выполнения какой-либо операции, что сложно, медленно и определенно неправильно.

Итак, каков правильный способ его хранения?