kos*_*tmo 9 algorithm clrs binary-search-tree
我想知道在计算机科学背景下对"祖先"定义的共识是什么.
我只是问,因为在算法导论,第二版,p.259有一个Tree-Successor(x)看似奇怪的算法的描述.在寻找节点x的后继者时,
[...]如果节点的右子树X是空的,X有一个继任Ÿ,然后ÿ是最低的始祖X,其左子也是祖先X.
在具有关键根二叉搜索树2和孩子1和3,的继任者1是其母公司2.在这种情况下,x是x的后继者y的左子.根据这本书的定义,x必须是它自己的祖先,除非我遗漏了什么.
关于这一点,我没有在勘误表中找到任何内容.
Shr*_*saR 15
这只是一个定义问题,但在这种情况下,是的.CLRS将x的祖先定义为从根到x的唯一路径上的任何节点,根据定义,该节点包括x.
你引用的句子片段首先提到下一页的练习12.2-6,它指定了这个:
(回想一下,每个节点都是它自己的祖先.)
:-)