Способ копирования и хранения всех записей в сбалансированном двоичном дереве поиска с помощью O (1)

Question

Я реализую двоичное дерево поиска в C++ 11. Я хочу добавить функцию, которая позволяет отмечать разные версии структуры данных с постоянной временной сложностью.

Что я думал о добавлении другого свойства в корневой узел под названием «имя», «ключ» или «отметка» - таким образом, доступ к O (1). Но, чтобы сохранить версию дерева я бы

1. создать копию корня (я думал о создании нового экземпляра двоичного дерева поиска и просто присвоить дерево, я хочу, чтобы скопировать этот новый экземпляр)
2. хранить скопированный корень в массиве

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

Ниже представлен небольшой эскиз, иллюстрирующий процесс.

Большое спасибо за вашу помощь.

FunkyPeanut

Answer 1

Я думаю, что вы после этого является persistent BST. Это позволяет «копировать» в O (1) время (просто скопировать указатель), выполняя все другие операции BST с теми же большими значениями времени, что и ванильный BST. Основное различие заключается в том, что операции, которые используются для вывода O (1), теперь занимают пространство O (lg n), по крайней мере, когда старая версия дерева была где-то сохранена.

(Вы можете реализовать постоянные структуры данных в C++ довольно легко с shared_ptr.)