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

Question

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

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

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

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

Я ничего не нашел в errata.

Answer 1

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

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

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

:-)

Answer 2

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

Не нормально, AFAIK. Например, на странице Википедии на binary trees, предком определяется следующим образом:

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

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

Answer 3

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