Энциклопедия Turbo Pascal. Главы 1-4
Страница 35. Использование двоичного дерева для организации разреженных массивов


Использование двоичного дерева для организации разреженных массивов

     Двоичное дерево  является по существу модифицированным спис-
ком с двойной связью. Основное его преимущество над обычным спис-
ком является быстрота поиска элемента,  и как следствие, быстрота
вставок и просмотров.  В тех случаях,  когда требуется обеспечить
быстрый поиск в связанном списке записей, применение двоичных де-
ревьев дает очень хорошие результаты.
     При использовании  двоичного дерева для реализации электрон-
ной таблицы, запись "cell" следует изменить следующим образом:
     CellPointer = ^cell;
     str9 = string[9];
     str128 = string[128];

     cell = record
       CellName: str9;
       formula: str128;
       left: CellPointer;
       right: CellPointer;
     end;

     Функцию "Stree", приведенную в главе 2, можно модифицировать
так, что дерево будет строиться по названию ячейки. Следует отме-
тить, что параметр "New" является указателем на новый элемент де-
рева.
     При вызове этой функции в качестве  первых  двух  аргументов
должен задаваться указатель корневой вершины, а в качестве треть-
его аргумента должен задаваться указатель на новую ячейку.
     В качестве результата выдается указатель корневой вершины.

          { вставка ячейки в дерево }

       function STree(root, r, New:CellPointer; data: char):
               CellPointer;
       begin
         if r = nil then
         begin
           New^.left := nil;
           New^.right := nil;
           if New^.Cellname < root^.Cellname
             then root^.left := New
             else root^.right := New;
             STree := New;
        end else
        begin
          if New^.Cellname<r^.Cellname then
          STree := STree(r,r^.left, New)
           else STree := STree(r, r^.right, New)
        end;
        Stree := root
       end; { конец процедуры STree }

     Для удаления ячейки из электронной таблицы следует модифици-
ровать функцию Dtree, в качестве ключа используя название ячейки:

          { удаление элемента из дерева }
         function DTree(root:Cellpointer;key:str9):Cellpointer;
         var
           temp,temp2:Cellpointer;

        begin
          if root^.CellName = key then
          begin
            if root^.left=root^.right tnen
            begin
              dispose(root)
              DTree := nil;
            end
            else  if root^.left=nil tnen
            begin
              temp := root^.right
              dispose(root)
              DTree := temp;
            end
            else  if root^.right=nil tnen
            begin
              temp := root^.left
              dispose(root)
              DTree := temp;
            end
            else
            begin  { имеются два листа }
              temp2 := root^.right
              temp := root^.right
              while temp^.left <> nil do temp := temp^.left;
              temp^.left := root^.left
              dispose(root);
              DTree := temp2
            end;
            else
            begin
              if root^.CellName < key
              then root^.right :=  DTree(root^.right, key)
              else root^.left :=  DTree(root^.left, key)
              DTree := root;
            end;
          end; { конец функции DTree }

     И наконец,  можно модифицировать функцию поиска для быстрого
нахождения ячейки по ее названию:

     { найти заданную ячейку и установить указатель на нее }
     function Search(root: CellPointer; key str9): CellPointer
     begin
       if root:=nil then Search :=  nil
       else begin
        while (root^.CellName<>key) and (root<>nil) do
        begin
          if root^.CellName<>key then root:=root^.left
          else root:=root^.right;
        end;
        Search :=  root;
     end; { конец процедуры поиска }


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

 
« Предыдущая статья