Итерация по бинарному дереву без контроля стека или динамического выделения

Question

Существует ли эффективный, практичный способ итерации по двоичному дереву с учетом следующих ограничений:

1. У вас нет контроля над стеком вызовов, и, следовательно, вы не можете использовать рекурсию. Все состояния должны находиться внутри объекта итератора / диапазона, а не в стеке.
2. Нигде в алгоритме нельзя использовать выделение кучи.
3. Дерево может быть неизменным, и поэтому вы не можете хранить внутри него состояние итерации.
4. У вас нет родительских указателей.
5. Структура итератора / диапазона не должна быть настолько большой, чтобы переходить к функциям было совершенно неразумно.

Edit:

1. Это не домашняя работа. Я на самом деле пытаюсь спроектировать библиотеку, которая строит двоичные деревья во втором стеке и дает много гарантий о распределении кучи (или ее отсутствии).
2. Деревья сбалансированы. (Это деревья AVL.)

Answer 1

Это может быть сделано только для деревьев до определенного предела по глубине (и, следовательно, по количеству элементов), поскольку для этого требуется вспомогательная память, пропорциональная глубине дерева; в то время, когда вы выполняете итерацию на элементе, вам нужно отслеживать, к какому элементу перейти к следующему, и если вы находитесь в одном из самых глубоких листьев, то количество требуемых «указателей отслеживания» будет всего на 1 меньше глубины дерева. Например, если вы можете принять ограничение глубиной 32 (и, следовательно, не более 4 294 967 295 узлов), потребуется вспомогательный массив фиксированного размера из 32 указателей (плюс индекс на нем).

Для двоичных деревьев, которые не являются полностью вырожденными (и, таким образом, имеют количество узлов, примерно пропорциональных 2**depth, а не только depth ;-), этот фиксированный объем вспомогательной памяти должен быть приемлемым, т.е. только что исправили вспомогательную память порядка log(N) указателей для итерации по любому дереву с N узлами. Если это не приемлемо, то ответ на ваш вопрос "есть ли ...?" нет ; -).

Answer 2

Если ваше дерево гарантированно отсортировано по его значениям и эти значения строго возрастают (все B> A, а не только B> = A), то вы можете обходить деревья неограниченного размера без использования динамической памяти. Вы, однако, получаете удар по производительности.

Чтобы найти следующее значение после значения A, просто снова спуститесь в дерево, выполняя бинарный (конечно) поиск значения, чуть большего, чем A.

Я только что это придумал. Если кто-то может доказать, что я ошибаюсь, продолжай!