Idiomatic Traversal Binary Tree (возможно, любое дерево)

Question

Doubly Linked List позволяет идиоматический обход связанного списка, и я подумал, почему бы не использовать двоичное дерево? Традиционно двоичные деревья или деревья в целом являются однонаправленными, и это означает, что при большом дереве с достаточным количеством узлов время работы для поиска листового узла может быть дорогостоящим.

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

Например, если я использовал внутренний класс

class Tree<T> { 

     private class TwoWayNode { 

      var data  : T 
      var left  : TwoWayNode 
      var right : TwoWayNode 
      var previous : TwoWayNode 
     } 
} 

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

Answer 1

Учитывая, что вы храните ссылку previous, вы можете сначала пройти влево. По прибытии на листовой узел, вы снова возвращаетесь назад, переходите вправо.

Вы всегда можете сравнить текущий узел, ваши «ходок», с дочерними узлами, так что вы можете проверить, если вы пошли оставило или право в последний раз. Это делает ваш обход без гражданства, и вам даже не нужна рекурсия; подходит для очень больших наборов данных.

Теперь, каждый раз, когда вы только что покинули правый лист, вы снова возвращаетесь.

Этот алгоритм является методом глубины-первого поиска. ^*

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

---

^*: http://en.wikipedia.org/wiki/Depth-first_search

Bonus: Эта статья на алгоритмы обхода для Kd деревьев в Ray Tracing: Обзор: Kd-обходе дерева Алгоритмы трассировки лучей (http://dcgi.felk.cvut.cz/home/havran/ARTICLES)/cgf2011.pdf

Answer 2

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

Но не всегда нужен родительский указатель:

• Для заказовМои-обхода можно использовать рекурсивный алгоритм так, что стек вызовов заботится о том, что для вас.
• Если вы хотите получить доступ к узлу min или max, вы можете просто сохранить дополнительный указатель на них.
• Иногда вы можете использовать finger tree.
• Или организовать указатели дополнительные умна (см Self adjusting binary search trees страница 666):
  • Левый указатель узла указывает на первый (слева) ребенка
  • Правый указатель узла указывает либо на собрата (если это левый ребенок) или назад к родителю (если это право ребенка)

Extra прохладное:Threaded бинарные деревья поиска для дополнительной легко симметричного (и в обратном порядке) обход без стека - так что O (1) место!