Использование итератора для клонирования BST быстрее, чем рекурсия?

Question

У меня возник вопрос о принципе проектирования Binary Sorted Tree.

Мне нужно создать глубокую копию Binary Expression Tree, и я выполняю это, пройдя все узлы в дереве и создавновый, идентичный.

У меня уже есть treeIterator, настроенный для других целей, и мне было интересно, будет ли итератор быстрее, медленнее или примерно с той же скоростью / использованием памяти, что и рекурсивно.

Спасибо!

Answer 1

Я думаю, что рекурсия будет быстрее.

Я не знаю точную реализацию вашего итератора, но я предполагаю, что она идет к каждому узлу? Если ваш BST основан на структуре корневого узла, то переход к каждому узлу (как в итераторе) будет медленнее, чем рекурсия.

Вот как я бы это реализовал:

Рекурсивный, Создайте новый корневой узел (идентичный исходному корневому узлу). Добавьте копии оригинального корневого левого и правого узлов. (Если они существуют)

Answer 2

Есть две части: (1) обход дерева и (2) создание новой копии дерева.Я предполагаю, что под итерацией вы подразумеваете цикл, который поддерживает позицию в дереве вручную.Вероятно, это быстрее / меньше памяти, чем рекурсия.Тем не менее, при создании нового дерева, вероятно, лучше использовать рекурсию и строить дерево по мере его прохождения.Если вы выполняете итерацию и вставляете узел в новое дерево, для которого требуется O (n lg n).С другой стороны, рекурсия займет всего O (n), хотя вы можете взорвать свой стек на очень глубоких деревьях.

Answer 3

Вы не указали, как будете реализовывать итератор.Итератор - это просто интерфейс, а не конкретная реализация.

Поиск в BST занимает O (log n) время, что означает, что в любой момент времени поиск следующего узла должензанять O (журнал N) время.

Объяснение: Следующий узел всегда является наименьшим элементом в правом поддереве или родительским узлом текущего узла.В любом случае, это не займет более log n времени.

Если ваша итерационная реализация не займет менее O (log n) времени, рекурсия будет быстрее.

Редактировать: Мне нужно указать, что здесь обозначение O для среднего случая, а не для худшего.Однако при условии, что у вас достаточно сбалансированное дерево, log n все равно должно применяться.