二叉树搜索的迭代版本

Question

基本树-在二叉搜索树中搜索节点(值为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≠keyx)而不是(while x≠NIL and k≠keyx)吗？

顺便说一句，如果你想知道，这是一本著名的算法分析书。

Answer 1

不，它需要为and，否则如果找不到k，您将取消引用NIL。请记住，只要表达式的计算结果为真，while就会执行。

while x ≠ NIL and k ≠ key[x]

如果x为NIL，则表达式x ≠ NIL and k ≠ key[x]为false，因为x ≠ NIL为false。and的任何一端为false都会导致整个表达式为false。

如果使用or，x ≠ NIL仍然是false，但您需要评估另一边- or的两端都必须为false，才能使or为false。不幸的是，评估另一端时会取消引用NIL。哦哦。即使不是因为这个问题，k ≠ key[x]也是真的(因为我们考虑的情况是找不到k，因此树x中的任何key都不能为k)。由于or的一个(或多个)侧为true，因此or的计算结果为true，循环将永远继续。

在英语中，while可以理解为: while tree (x ≠ NIL) 和我们还没有找到我们正在寻找(k ≠ key[x])。