Новости           

Программы

Turbo Pascal

Игры

Документация

"Странности"

FAQ

Ссылки

Благодарности

Гостевая книга

От автора

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

              Двоичное дерево  является по существу модифицированным спис-
         ком с двойной связью. Основное его преимущество над обычным спис-
         ком является быстрота поиска элемента,  и как следствие, быстрота
         вставок и просмотров.  В тех случаях,  когда требуется обеспечить
         быстрый поиск в связанном списке записей, применение двоичных де-
         ревьев дает очень хорошие результаты.
              При использовании  двоичного дерева для реализации электрон-
         ной таблицы, запись "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 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
         операций сравнений.




(с)Все права защищены

По всем интересующим вопросампрошу писать на электронный адрес

    Rambler's Top100 PROext: Top 1000
    Rambler's Top100 Яндекс цитирования
Hosted by uCoz