Узел в дереве, рассмотрел его собственного предка?
Я задаюсь вопросом, что согласие находится на определении "предка" в контексте информатики.
Я только спрашиваю потому что во Введении в Алгоритмы, Второй Выпуск, p. 259 существует описание алгоритма Tree-Successor(x) это кажется нечетным. В нахождении преемника узла x,
[...], если правильное поддерево узла x пусто, и x имеет преемника y, то y является самым низким предком x, покинутый ребенок которого является также предком x.
В дереве двоичного поиска с корнем, имеющим ключ 2 и дети 1 и 3, преемник 1 его родитель 2. В этом случае x является покинутым ребенком преемника x, y. Согласно определению книги, затем, x должен быть своим собственным предком, если я не пропускаю что-то.
Я ничего не нашел в опечатках об этом.
3 ответа
Это всего лишь вопрос определения, но в данном случае да. CLRS определяет предка x как любой узел на уникальном пути от корня к x, который по определению включает x.
Процитированный вами фрагмент предложения начинается с упоминания упражнения 12.2-6 на следующей странице, которое определяет следующее:
(Вспомним, что каждый узел является своим предком.)
:-)
Считается ли узел в дереве своим собственным предком?
Обычно нет, AFAIK. Например, на странице Википедии о бинарных деревьях , предок определяется следующим образом:
Если существует путь от узла p к узлу q, где узел p ближе к корню node, чем q, то p является предком q, а q является потомком p.
Но очевидно, что определение предка в том учебнике таково, что узел является своим собственным предком. Это определение не совсем интуитивно понятно, но учебник может свободно вводить собственные определения используемой терминологии. Возможно, это определение упрощает некоторые связанные описания / теоремы / и т. Д.
Нет, узел не является предком самого себя. По моему мнению, это должно быть так: если правое поддерево узла x пусто и у x есть преемник y, то y является младшим предком x, чей левый потомок либо x, либо предок x. , но код, приведенный в книге, предположительно относится к подобным случаям.