Структуры и алгоритмы обработки данных

       

Процедура поиска по бинарному дереву


Назначение этой процедуры в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции поиска (число узлов, которое надо перебрать для этой цели) зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список (иметь единственную ветвь) - такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их ключей, например :

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. в среднем придется перебрать 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



Содержание раздела