Итерационный обход бинарных деревьев

Архив 2014/15
#1

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

На просторах интернета я обнаружил два способа реализации подобного алгоритма:

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

Второй метод я и реализовал в прикреплённом коде.

Не могу назвать асимптотическую сложность по времени этого алгоритма. Очевидно, что он медленнее рекурсивного, так как нам приходится “бродить” по дереву в поисках ещё не пройденного узла. Зато мы получаем сложность по памяти !!!(не учитывая того, что у нас n указателей на родителя)

Интересные ссылки: Хабрахабр Осторожно java! Wikipedia Осторожно красивые картинки!

traversal.pas (3.4 КБ)

#2

Если количество указателей зависит от дерева, то это уже не O(1) по памяти.

#3

Если делали по картинкам, то $O(n)$: по каждому ребру проходим ровно два раза.

Неа, там один указатель. Сначала спускаемся до наименьшего элемента, после делаем iterator++ пока не дойдем до наибольшего, а затем поднимаемся до корня.

#4

Имеется в виду, что размещение данных в структуру дерева сразу приводит к расходам по памяти O(n), поскольку с каждым элементом данных ассоциирован узел, включающий несколько указателей.

Если считать, что дерево – это и есть входные данные, то, наверное, вы правы.

#5

Естественно, само дерево в оценке алгоритма обхода считаться не должно. Это если бы у нас был алгоритм сортировки массива, скажем, а мы внутри дерево создавали, то оно бы считалось.

#6

Согласен. Не правильно понял первый ответ.

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

#7

А, ну вот я и писал вначале: если используется O(n) указателей, то сложность по памяти O(n). Не вижу каких-то аргументов против. Это @kvark161 сбивает с толку.

#8

В прикрепленной реализации есть указатель на предка, поэтому можно реализовать за $O(1)$ памяти.

#9