Энциклопедия Turbo Pascal. Главы 1-4 - Использование двоичного дерева для организации разреженных массивов
ОГЛАВЛЕНИЕ
Использование двоичного дерева для организации разреженных массивов
Двоичное дерево является по существу модифицированным списком с двойной связью. Основное его преимущество над обычным списком является быстрота поиска элемента, и как следствие, быстрота вставок и просмотров. В тех случаях, когда требуется обеспечить быстрый поиск в связанном списке записей, применение двоичных деревьев дает очень хорошие результаты.
При использовании двоичного дерева для реализации электронной таблицы, запись "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 операций сравнений.