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

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 

Если не первая линия (итерационного алгоритма) на самом деле быть в то время как (х ≠ NIL или к ≠ ключ [х]) вместо (при х ≠ NIL и k ≠ [x])?

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

Answer 1

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

while x ≠ NIL and k ≠ key[x] 

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

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

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