Процедура поиска по бинарному дереву
Назначение этой процедуры в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции поиска (число узлов, которое надо перебрать для этой цели) зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список (иметь единственную ветвь) - такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их ключей, например :
В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. в среднем придется перебрать N/2 элементов.
Наибольший эффект использования дерева достигается в том случае, когда дерево "сбалансировано". В этом случае для поиска придется перебрать не более LOG2N элементов.
Опишем процедуру поиска. Переменной search будет присваиваться указатель на найденное звено :
p=tree
WHILE p<>nil DO
IF key=k (p)
THEN search=p
RETURN
END IF
IF key<>k (p)
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
search=nil
RETURN
