Итерационная версия поиска двоичного дерева

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

Разве первая строка (итерационного алгоритма) не должна быть в то время как (x ≠ NIL ИЛИ k ≠ key [x]) вместо (тогда как x ≠ NIL и k ≠ key [x])?

Кстати, если вам интересно, это из одной из знаменитых книг Алгоритм анализа.

Answer 1

Нет, оно должно быть and, так как в противном случае вы будете разыменовывать NIL, если k не найден. Помните, что while выполняется до тех пор, пока выражение принимает значение true.

while x ≠ NIL and k ≠ key[x]

Если x равен NIL, то выражение x ≠ NIL and k ≠ key[x] равно false, поскольку x ≠ NIL равно false. Любая сторона ложного and делает все выражение ложным.

Если вместо этого использовать or, x ≠ NIL будет по-прежнему ложным, но вам нужно будет оценить другую сторону - обе стороны or должны быть ложными, чтобы or было ложным. К сожалению, оценивая другую сторону разыменования NIL. По электронной почте Ой. Даже если бы не эта проблема, k ≠ key[x] верно (потому что мы рассматриваем случай, когда k не найден, поэтому key в дереве x не может быть k). Поскольку одна (или более) сторон or имеет значение true, or оценивается как true, и цикл продолжается вечно.

На английском языке this while может читать: пока еще осталось дерево (x ≠ NIL) и , мы еще не нашли то, что ищем (k ≠ key[x]).