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

Question

Мне интересно, что такое консенсус по определению «предка» в контексте информатики.

Я спрашиваю только потому, что в Введение в алгоритмы , второе издание, с. 259 есть описание алгоритма Tree-Successor(x), которое кажется странным. В поиске наследника узла x ,

[...] если правое поддерево узла x пусто и x имеет преемника y , тогда y является самым низким предком x , чей левый ребенок также является предком x .

В бинарном дереве поиска с корнем, имеющим ключ 2 и потомками 1 и 3, наследник 1 является его родителем 2. В этом случае x является левым потомком наследника x , y . Согласно определению книги, x должно быть его собственным предком, если я что-то упустил.

Я не нашел ничего в опечатках об этом.

Answer 1

Это просто вопрос определения, но в данном случае да . CLRS определяет предка x как любой узел на уникальном пути от корня до x, который по определению включает x.

Фрагмент предложения, который вы процитировали, начинается с упоминания упражнения 12.2-6 на следующей странице, где указано следующее:

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

: -)

Answer 2

Является ли узел в дереве своим собственным предком?

Обычно не так, AFAIK.Например, на странице Википедии о двоичных деревьях , предок определяется следующим образом:

Если существует путь от узла p к узлу q, где узелp ближе к корневому узлу, чем q, тогда p является предком q, а q является потомком p.

Но очевидно, что определение предка в учебнике таковочто узел является его собственным предком.Это определение не совсем интуитивно понятно, но учебник может свободно вводить свои определения терминологии, которую он использует.Возможно, это определение упрощает некоторые связанные описания / теоремы и т. Д.

Answer 3

Нет, узел не является предком самого себя.По моему мнению, это должно быть так: если правое поддерево узла x пусто и x имеет преемника y, то y является самым низким предком x, чей левый потомок равен either x or an ancestor of x., но код, приведенный в книге, предположительно обрабатывает такой тип:случаи.