3

二分探索木でノード (値 k を持つ) を検索するための基本的な木探索アルゴリズム。「x」は、二分探索木のノードを示します。

TREE-SEARCH (x, k)
 if x= NIL or k = key[x]
    then return x
 if k < key[x]
    then return TREE-SEARCH(left[x], k)
    else return TREE-SEARCH(right[x], k)

反復バージョン:

ITERATIVE-TREE-SEARCH(x, k)
 while x ≠ NIL and k ≠ key[x]
     do if k < key[x]
           then x ← left[x]
           else x ← right[x]
 return x

（反復アルゴリズムの）最初の行は、実際には while (x ≠ NIL OR k ≠ key[x]) ではなく (while x ≠ NIL and k ≠ key[x]) であるべきではありませんか?

ちなみに、これはアルゴリズム分析の有名な本の 1 つからのものです。

4

1 に答える 1

2

いいえ、そうでなければ、が見つからないand場合に NIL を逆参照するため、そうする必要があります。式が true と評価される限り、kが実行されることに注意してください。while

while x ≠ NIL and k ≠ key[x]

x が NIL の場合、x ≠ NIL and k ≠ key[x]is false であるため、式はx ≠ NILfalse です。どちらかandが偽であると、式全体が偽になります。

or代わりに が使用された場合x ≠ NILでも false になりますが、反対側を評価する必要があります — が false であるためには、 an の両側orが false でなければなりませんor。残念ながら、反対側を評価すると NIL が逆参照されます。おっと。その問題がなかったとしても、k ≠ key[x]は真です (k が見つからない場合を考えているためkey、ツリーの no は にxなる可能性がありますk)。の 1 つ (または複数) の側面orが true であるため、 は true とor評価され、ループは永遠に続きます。

英語では、while は次のように読むことができx ≠ NILます。k ≠ key[x]

于 2009-10-01T06:55:24.013 に答える