Je me demande quel est le consensus sur la définition de "ancêtre" dans un contexte scientifique informatique.
Je ne demande que parce que dans Introduction aux algorithmes , deuxième édition, p. 259 Il y a une description de l'algorithme [...] si le bon sous-arbre de noeud x est vide et x a un successeur y , puis y est l'ancêtre le plus bas de x dont l'enfant gauche est également un ancêtre de x .
dans un arbre de recherche binaire avec une racine ayant une clé Je n'ai rien trouvé dans le errata à ce sujet. Tree-successeur (x) qui semble impair. En trouvant le successeur du noeud x ,
2 et des enfants 1 et 3 , le successeur de 1 est son parent 2 . Dans ce cas, x est l'enfant gauche du successeur X , y . Selon la définition du livre, x doit être sa propre ancêtre, sauf si je manque quelque chose.
3 Réponses :
est un nœud dans un arbre considéré comme son propre ancêtre?
Pas normalement, Afaik. Par exemple, dans la page Wikipedia sur arbres binaires , ancêtre est défini ainsi:
Si un chemin existe du nœud P au noeud Q, où le nœud P est plus proche du nœud racine que Q, puis p est un ancêtre de Q et Q est un descendant de p.
Mais apparemment, la définition du livre de texte ancêtre est telle qu'un nœud est sa propre ancêtre. Cette définition n'est pas exactement intuitive, mais un manuel est libre d'introduire ses propres définitions pour la terminologie qu'elle utilise. Peut-être que cette définition simplifie certaines des descriptions / théorèmes apparentées / etc.
Non, un nœud n'est pas ancêtre de lui-même. Selon moi, il devrait être: si le sous-arbre droit du nœud X est vide et X a un successeur Y, alors y est l'ancêtre le plus bas de x dont l'enfant gauche est X ou un ancêtre de x. mais le code donné dans le livre supposé manipuler un tel type de cas.
C'est simplement une question de définition, mais dans ce cas, oui . Les CLRS définissent un ancêtre de X comme n'importe quel noeud sur le chemin unique de la racine à x, qui comprend x.
Le fragment de phrase que vous avez cité commence par mentionner l'exercice 12.2-6 à la page suivante, qui spécifie ceci:
(rappelez-vous que chaque nœud est son propre ancêtre.)
: -)
Cela doit être la réponse la plus précise sur le Web: D
Donc, la chanson va, YouTube.com/watch?v=w7x1etPkzsk