24. Дерево поиска. Процедуры поиска, включения и исключения элементов для дерева поиска. Временная сложность этих процедур

 

 

            Предположим теперь, что наши данные должны иметь динамическую структуру. Тогда массив для их представления не годится. Вместе с тем, информацию следует организовать таким образом, чтобы поиск элемента по заданному ключу осуществлялся так же быстро, как и при дихотомическом поиске. Подходящей структурой для представления таких данных является дерево поиска.

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

            Возможности динамического размещения переменных с доступом к ним через ссылки позволяют легко менять саму структуру дерева, т.е. дерево “растет” или “сокращается” в ходе выполнения программы.

            Элемент дерева поиска опишем с помощью следующих типов:

            type     ptr=^b_tree;

                        b_tree=record             info:string;      left, right:ptr               end;

 

            2.1. Нахождение элемента с данным ключом в дереве поиска

 

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

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

function locate(y:integer, p:ptr): ptr;

 begin 

            while (p<>nil) and (p^.key<>y) do

                        begin   if (y < p^.key) then p:=p^.left           else p:=p^.right;

            locate:=p

 end;

            Вызов функции locate осуществляется с параметрами (y, root), где root - указатель на корень дерева поиска. Если элемента с ключом y в дереве обнаружено не было, то функция locate(y,root) примет значение nil.

 

            2.2. Включение элемента в дерево поиска ...

... рассмотрим на примере следующей задачи.

            Задача.2.2.  В данной последовательности целых чисел определить частоту вхождения каждого из этих чисел.

            Решение. Создаем  пустое бинарное дерево. В записи, соответствующей вершине дерева, заменяем информативное поле info:string на поле счетчика count:integer. Прочитав очередное число - ключ y, ищем его в дереве поиска. Если элемент с ключом y в дереве уже существует, то увеличиваем счетчик его вхождений count на единицу. Если же, спустившись по пути поиска до концевой вершины V, элемент с ключом y мы не нашли, то создаем новую вершину с начальным единичным значением счетчика, “цепля” ее

·      слева от вершины V, если y меньше ключа вершины V, или

·      справа от вершины V, если y больше ключа вершины V.

            Этот процесс называется поиском по дереву с включением.

            На рис. 2.1 представлен программный блок, решающий задачу 2.2.

                                   ...

procedure search (y: integer; var p:ptr);

begin

            if p=nil then {* элемента с данным ключом в дереве нет; включение*}

               begin                        new(p); p^.key:=y; p^.count:=1; p^.left:=nil; p^.right:=nil              end

            else

               begin              

                           if (y<p^.key) then search(y, p^.left)

                                   else

                                      if (y>p^.key) then search(y, p^.right)

                                               else  {*x=p^.key*}                Inc(p^.count)

               end

 end; {* search *}

BEGIN

            root:=nil {* root – указатель на корень дерева поиска *};

            read(n); {* n – количество чисел в данной последовательности *}

            while n>0 do

                        begin   read(keyword); search(keyword, root); n:=n-1         end

END.

            ...

Рис. 2.1.

 

            2.3. Исключение элемента из дерева поиска

 

            В случае исключения элемента из дерева поиска возможны три ситуации: удаляется

1.    концевая вершина

2.    вершина с одним потомком

3.    вершина с двумя потомками.

            Первые две ситуации не вызывают трудностей и обрабатываются одинаково. Пусть, например, удаляемая вершина находится по адресу p и пусть, для определенности, она имеет левого потомка. Тогда удаления вершины осуществляется с помощью трех следующих операторов:

            q:=p;    p:=p^.left;       dispose (q);.

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

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

            Рассмотрим более подробно процесс преобразования дерева поиска после удаления вершины с двумя потомками. Пусть удаляется вершина V, имеющая двух потомков. Тогда поиск замещающего элемента W (самого правого элемента левого поддерева вершины V) осуществляется следующим образом: спускаемся вдоль самой правой ветви левого поддерева вершины V до тех пор, пока не найдем вершину W с нулевым правым указателем: right=nil. После этого заменяем вершину V на W, “цепляя” единственного потомка вершины W (если он есть) к предку этой вершины.

            Рис. 2.2 иллюстрирует процедуру преобразования дерева поиска после удаления вершины: на рис. 2.2, а показано дерево поиска до удаления вершины с ключом 10, а на рис. 2.2, б - после ее удаления

            Рис. 2.2.

 

§ 2.4. Оценка сложности при работе с деревом поиска

 

Дерево называется идеально сбалансированным, если число вершин в его ЛПД и ППД отличается  не более чем на 1. Приблизительно подсчитаем высоту h идеально сбалансированного дерева с n вершинами:

20+21+22+...+2h  = » n, откуда 2h » , т.е. при достаточно больших значениях n:

h = O (log2 (n)).

            При построении дерева поиска с помощью алгоритма поиска с включением заранее неизвестно, как будет расти дерево и какую форму оно примет.

            В лучшем случае дерево поиска окажется идеально сбалансированным. Высота этого дерева определит максимальную сложность операций поиска, включения и удаления элементов, которая составит, таким образом,         Tmax(n) = O (log2 (n)).

            Однако в худшем случае, когда все поступающие из входного потока ключи идут в порядке неубывания (или невозрастания), дерево выродится в обычный линейный список и максимальная сложность операций поиска, включения и удаления элементов составит Tmax(n)=O(n), т.е. все преимущества дерева поиска по сравнению с линейным списком будут утрачены.

            Доказано, что затраты на перестройку случайного дерева в идеально сбалансированное себя не оправдывают, т.к. они гасят выигрыш в длине пути.

            Однако менее строгое определение сбалансированности (см. следующий параграф) позволяет создать более простую процедуру переупорядочения за счет лишь незначительного усложнения процедуры поиска.