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




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


Назначение его в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рис. 5.8.

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать N/2 элементов.

Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано.В этом случае для поиска придотся перебрать не больше log2N

элементов.

Строго сбалансированное дерево - это дерево, в котором каждый узел имеет левое и правое поддеревья, отличающиеся по уровню не более, чем на единицу.

Поиск элемента в бинарном дереве называется бинарным поиском по дереву.

Такое дерево называют деревом бинарного поиска.

Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше - правое.

Пусть задан аргумент key

p = tree

whlie p <> nil do

  if key = k(p) then

    search = p

    return

  endif

  if key < k(p) then

    p = left(p)

  else

    p = right(p)

  endif

endwhile

search = nil

return

p := tree;

whlie p <> nil do

  begin

    if key = p^.k then

      begin

        search := p;

        exit;

      end;

    if key < p^.k then

      p := p^.left

    else

      p := p^.right;

  end;

search := nil;




Содержание  Назад  Вперед