Эффективность поиска по бинарному дереву

Эффективность поиска по бинарному дереву

Назначение его в том, чтобы по заданному ключу осу­ществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вы­рождено в однонаправленный список, как правое на рис. 5.8.Рис. 5.8. Бинарные деревья.В этом случае время поиска будет такое же, как и в од­нонаправленном списке, т.е. придется перебирать N/2 эле­ментов.Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано. В этом случае для поиска придется перебрать не больше log N элементов.Строго сбалансированное дерево - это дерево, в котором каждый узел имеет левое и правое поддеревья, отличающиеся по уровню не более чем на единицу.Поиск элемента в бинарном дереве называется бинар­ным поиском по дереву.Такое дерево называют деревом бинарного поиска.Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше инфор­мационного поля вершины, то анализируем левое поддерево, больше - правое.

31. Алгоритмы прохождения бинарных деревьев

В зависимости от последовательности обхода подде­ревьев различают три вида обхода (прохождения) деревьев (рис.4.9):

Рис. 4.9. Прохождение бинарных деревьев

1. Сверху вниз А, В, С.

2. Слева направо или симметричное прохождение В, А, С.

3. Снизу вверх В, С, А.

Неформальный итерационный алгоритм обхода дерева:

1. Если обработка производится после 1-го захода в узел, то это – обход сверху вниз.ABDECF

2. Если обработка производится после 2-го захода в узел, то это – обход слева направо.DBEACF

3. Если обработка производится после 3-го захода в узел, то это – обход снизу вверх.DEBFCA

Наиболее часто применяется второй способ. Ниже приведены рекурсивные алгоритмы прохождения бинарных деревьев.

Procedure pretrave (tree tnode) Begin if tree <> nil then begin WriteL(Tree^.Info); Pretrave(Tree^.left); Pretrave(Tree^.right);End;end;

procedure intrave (tree: tnod) begin if tree <> nil then begin intrave(Tree^.left);writeLn(Tree^.info);intrave(Tree^.right);end;end;

Рис. 4.10 Обход дерева А, В, С

Поясним подробнее рекурсию алгоритма обхода дерева слева направо.

Пронумеруем строки алгоритма intrave (tree):

1 if tree <> ml

2 then intrave (left(tree))

3 print info (tree)

4 intrave (right (tree))

5 endif

6 return

Обозначим указатели: t → tree; l → left; r → right

На приведенном рис. 4.11 проиллюстрирована последо­вательность вызова процедуры intrave (tree) по мере обхода узлов простейшего дерева, изображенного на рис. 4. 10.

Рис. 4.11. Иллюстрация рекурсивной работы процедуры intrave (tree) при обходе дерева на рис.4.10.