11

コンピュータサイエンスの文脈における「祖先」の定義についてのコンセンサスは何であるのか疑問に思います。

アルゴリズム入門、第2版、p。Tree-Successor(x)259奇妙に思われるアルゴリズムの説明があります。ノードxの後継を見つける際に、

[...]ノードxの右側のサブツリーが空で、xに後続のyがある場合、yはxの最も低い祖先であり、その左側の子はxの祖先でもあります。

2キーと子1を持つルートを持つ二分探索木では3、の後続1はその親2です。この場合、xはx後継子yの左の子です。したがって、本の定義によれば、私が何かを見逃していない限り、xはそれ自体の祖先でなければなりません。

これについての正誤表には何も見つかりませんでした。

4

3 に答える 3

19

これは単に定義の問題ですが、この場合はそうです。CLRSは、xの祖先を、ルートからxまでの一意のパス上の任意のノードとして定義します。これには定義上xが含まれます。

引用した文の断片は、次のページの演習12.2-6に言及することから始まります。これは、次のことを指定しています。

(すべてのノードが独自の祖先であることを思い出してください。)

:-)

于 2010-06-20T04:33:22.773 に答える
7

ツリー内のノードはそれ自体の祖先と見なされますか?

通常ではありませんが、AFAIK。たとえば、二分木のウィキペディアのページでは、祖先は次のように定義されています。

ノードpからノードqへのパスが存在し、ノードpがqよりもルートノードに近い場合、pはqの祖先であり、qはpの子孫です。

しかし、どうやらその教科書の祖先の定義はノードがそれ自身の祖先であるようなものです。この定義は正確には直感的ではありませんが、教科書では、使用する用語の独自の定義を自由に紹介できます。たぶん、この定義は、関連する説明/定理などのいくつかを単純化します。

于 2010-06-20T04:14:23.647 に答える
-2

いいえ、ノードはそれ自体の祖先ではありません。私によると、ノードxの右側のサブツリーが空で、xに後続のyがある場合、yはxの最も低い祖先であり、その左の子はeither x or an ancestor of x.、おそらくそのようなタイプのケースを処理する本に記載されているコードです。

于 2010-06-20T04:23:22.670 に答える