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