2017-01-02 8 views
0

Почему узлы двоичного дерева имеют ссылки только от родителя к детям? Я знаю, что есть резьбовое двоичное дерево, но их сложнее реализовать. Двоичное дерево с двумя ссылками позволит обход в обоих направлениях итеративно без стека или очереди.Почему узлы двоичного дерева имеют ссылки только от родителя к детям?

Я не знаю такого дизайна. Если есть, пожалуйста, дайте мне знать.

Редактировать 1: Позвольте мне вызвать проблему для этого. Я хочу сделать обход без рекурсии и без использования дополнительной памяти в виде стека или очереди.

PS: Я боюсь, что я получу чешуйку и ниспадаю за этот глупый вопрос.

+0

Проблемы, для которых хорошо подходит древовидная структура, не требуют таких двухсторонних обходов. Если вы сообщите нам, какая у вас проблема, возможно, кто-то может сделать предложение. –

+0

Нет. Я не пытаюсь решить проблему. Это был просто вопрос, который приходил на ум. Дело в том, что если мы представляем дерево таким образом, то мы также можем использовать как связанный список. – user902384

+0

@TimBiegeleisen как introsort и timsort - гибридный алгоритм сортировки. Возможно, у нас может быть гибридная структура данных. – user902384

ответ

1

Некоторые бинарные деревья требуют, чтобы дети не отставали от своих родителей или даже их прародителей, например. Splay Trees. Однако это только для балансировки или воспроизведения дерева. Причина, по которой мы проходим только дерево от родителя к детям, состоит в том, что мы обычно ищем определенный узел и до тех пор, пока бинарное дерево реализовано таким образом, чтобы все оставшиеся дети были меньше родительского, а все правильные дети больше чем родительский (или наоборот), нам нужны только ссылки в одном направлении, чтобы найти этот узел. Мы начинаем поиск в корне, а затем итерируем вниз, и если узел находится в дереве, мы можем его найти. Если мы начнем с листа, нет гарантии, что мы найдем нужный нам узел, вернувшись к корню. Причина, по которой у нас нет ссылок от ребенка к родительскому, заключается в том, что для поиска нет необходимости. Надеюсь это поможет.

+0

Можете ли вы сослаться на место, где было показано дерево пауз, имеющее двухсторонние ссылки. – user902384

+0

Хотя я согласен с тем, что основная цель деревьев заключается в поиске, но это ограничивает его полезность в том, что предлагает связанный список. Я пытаюсь убить двух зайцев одним выстрелом. – user902384

+0

Двоичные деревья лучше для поиска, потому что они быстрее. Что именно вы пытаетесь выполнить с вашим двоичным деревом помимо поисков? Ниже приведена ссылка в виде таблицы: http://cs.stackexchange.com/questions/1229/why-does-the-splay-tree-rotation-algorithm-take-into-account-both-the-parent- и – Luke1195

0

Может быть, однако, мы должны учитывать баланс между использованием памяти и сложностью.

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

Какое дерево двоичного поиска хорошее в том, что оно может реализовать множество проблем поиска в O (logN). Это достаточно быстро и экономит память.

+0

Правда, но сложность кода намного меньше. – user902384

0

Позвольте мне вызвать проблему для этого. Я хочу сделать обход без рекурсии и без использования дополнительной памяти в виде стека или очереди.

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

Они добавляют O (N) память к дереву для хранения родительского указателя, чтобы не использовать O (log N) в процессе рекурсии.

Какие родительские указатели позволяют нам поддерживать API, посредством которого вызывающий может передать указатель на узел и запросить операцию на нем, например, «найти следующий узел по порядку» (например).

В этой ситуации у нас нет стека, который содержит путь к корню; мы просто получаем узел «из синего» от вызывающего. С родительскими указателями, заданными узлом дерева, мы можем найти его преемника в амортизированном постоянном времени O (1).

Реализации, не требующие этой функции, могут сэкономить место, не включая родительские указатели в дереве, и использовать рекурсию или явную структуру стека для обхода корня для обхода листа.

+0

Да, у меня есть. Узел Say содержит структуру, которая составляет 1 КБ, а указатель - 8 байт, тогда он дешевле. – user902384

+0

Относительный размер данных узла и указателей не влияет на служебные данные памяти O (N) (сохраненные родительские указатели) по сравнению с O (log N) (пространство обратного трассировки при обходе от корня к листу). Большие данные просто делают проблему менее значительной. Добавление родительского указателя к дереву с миллионным узлом означает 8 миллионов байт: 8 мегабайт. Для сбалансированного дерева из миллиона узлов требуется глубина около 20 для обхода: крошечное количество накладных расходов для родительских указателей в стеке. Вы сохраняете 8 мегабайт, не сохраняя родительские указатели в дереве. Если это 8 мегабайт из 8 гигабайт, вам может быть все равно. – Kaz

Смежные вопросы