search - 二叉树搜索的迭代版本

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 ≠ key[x]) 而不是 (while x ≠ NIL and k ≠ key[x]) 吗？

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

Answer 1

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

while x ≠ NIL and k ≠ key[x]

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

如果使用 or，x ≠ NIL 仍然为 false，但您需要评估另一边 - or 的两边 必须为 false，or 才会为 false。不幸的是，评估另一方会取消引用 NIL。哎呀。即使不是因为这个问题，k ≠ key[x] 也是 true(因为我们正在考虑找不到 k 的情况，所以没有 key在树中x可以是k)。由于 or 的一侧(或多侧)为 true，因此 or 的计算结果为 true，并且循环将永远继续。

在英语中， while 可以读作:虽然还有树剩余 (x ≠ NIL) and 我们还没有找到我们要找的东西 ( k ≠ key[x])。