- •Введение
- •1. Структуры данных: деревья
- •1.1 Структуры данных
- •1.2 Деревья
- •1.3 Бинарные деревья
- •1.4 Бинарные деревья поиска
- •1.5 Красно-черные деревья
- •1.6 Операции над красно-черными деревьями
- •1.6.1 Повороты
- •1.6.2 Вставка
- •1.6.3 Удаление
- •1.6.4 Поиск узла с заданным ключом
- •1.6.5 Поиск минимума и максимума
- •2. Автоматизация операций над красно-чёрными деревьями
- •Заключение
- •Список литературы:
- •Приложение 1. Листинг программы
Заключение
В процессе выполнения работы были решены следующие задачи:
рассмотрены красно-чёрные деревья и их свойства;
изучены основные операции над красно-чёрными деревьями;
представлена реализация основных операций над красно-чёрными деревьями на алгоритмическом языке;
проиллюстрированы примеры красно-чёрных деревьев, а так же операции над ними;
произведена автоматизация основных операций над красно-чёрными деревьями.
В заключение курсовой работы можно сделать вывод, что красно-чёрные деревья это наиболее оптимальный способ представления структур данных, обеспечивающий быстрый поиск нужной информации. Автоматизация основных операций над красно-чёрными деревьями с использованием объектно-ориентированного программирования позволяет упросить работу с деревьями и даёт возможность расширять область применения, не переделывая программу, а лишь добавляя в неё новые уровни иерархии.
Красно-чёрные деревья составляют неотъемлемую часть современного информационного пространства, а также имеют широкую сферу применения. Поэтому изучение красно-чёрных деревьев, их основных свойств и операций над ними помогает изучить сферу их использования.
Список литературы:
АЛГОРИТМЫ МЕТОДЫ ИСХОДНИКИ[электронный ресурс]. – Режим доступа: http://algolist.manual.ru/ds/rbtree.php.
Кнут Д.Э. Искусство программирования. Том 2. Получисленные алгоритмы: Пер. с англ. - М.: «Вильямс», 2000. — 682с.
Кормен, Томас X., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М.: Издательский дом "Вильяме", 2005. - 1296 с.: ил. - Парал. тит. англ.
Поляков Д.Б., Круглов И.Ю.. Программирование в среде Турбо Паскаль (версия 5.5): Справ.-метод. пособие. – М.: Изд-во МАИ, 1992. – 576 с.
[электронный ресурс]. – Режим доступа: http://mathc.chat.ru/a3/articl03.htm.
Pascal Page[электронный ресурс]. – Режим доступа: http://volvo71.narod.ru/faq_folder/rb_tree.htm.
Приложение 1. Листинг программы
Program rbtree_k;
uses crt;
type
string_20 = string[20];
PTreeNode = ^TreeNode;
TreeNode = object
public
constructor init(_s: string; _parent: PTreeNode);
public
Color: integer;
left,right,parent,duplicates: PTreeNode;
data_string: string_20;
deleted: boolean;
end;
RBTree = object
public
constructor init;
destructor done;
function Search(s: string): integer;
function SearchFirstMatch(s: string): PTreeNode;
procedure Insert(s: string);
function InsertItem(s: string; node: PTreeNode): PTreeNode;
function Remove(s: string): boolean;
procedure SaveToFile(var f: text);
function LeftDepth: integer;
function RightDepth: integer;
function NumberOfLeaves(p: PTreeNode): integer;
public
root: PTreeNode;
private
procedure LeftRotation(node: PTreeNode);
procedure RightRotation(node: PTreeNode);
function TreeDepth(p: PTreeNode): integer;
procedure DeleteTree(p: PTreeNode);
procedure SaveNode(level: integer;
const node: PTreeNode; var f: text);
end;
Const
node_Red = 1;
node_Black = 0;
constructor TreeNode.init(_s: string; _parent: PTreeNode);
begin
data_string := _s;
left := nil; right := nil;
parent := _parent;
Duplicates := nil;
Color := node_Red;
Deleted := False;
end;
function compare(s1, s2: string): integer;
procedure trim(var s: string);
begin
while s[length(s)] = ' ' do delete(s, length(s), 1);
end;
begin
trim(s1); trim(s2);
if s1 < s2 then compare := -1
else if s1 > s2 then compare := +1
else compare := 0;
end;
constructor RBTree.init;
begin
root := nil;
end;
destructor RBTree.done;
begin
DeleteTree(Root);
end;
procedure RBTree.DeleteTree(p: PTreeNode);
begin
if p <> nil then begin
DeleteTree(p^.Left);
DeleteTree(p^.Right);
DeleteTree(p^.Duplicates);
dispose(p);
end;
p := nil;
end;
procedure RBTree.Insert(s: string);
var
node, node_2: PTreeNode;
begin
node := InsertItem(s, root);
if node = nil then exit;
while(node <> root) and (node^.parent^.color = node_Red) do begin
if node^.parent = node^.parent^.parent^.left then begin
node_2 := node^.parent^.parent^.right;
if (node_2 <> nil) and (node_2^.Color = node_Red) then begin
node^.parent^.Color := node_Black;
node_2^.Color := node_Black;
node^.Parent^.Parent^.Color := node_Red;
node := node^.Parent^.Parent;
end
else begin
if Node = Node^.Parent^.Right then begin
Node := Node^.Parent;
LeftRotation(Node);
end;
Node^.Parent^.Color := node_Black;
Node^.Parent^.Parent^.Color := node_Red;
RightRotation(Node^.Parent^.Parent);
end;
end
else begin
node_2 := Node^.Parent^.Parent^.Left;
if(node_2 <> nil) and (node_2^.Color = node_Red) then begin
Node^.Parent^.Color := node_Black;
Node_2^.Color := node_Black;
Node^.Parent^.Parent^.Color := node_Red;
Node := Node^.Parent^.Parent;
end
else begin
if Node = Node^.Parent^.Left then begin
Node := Node^.Parent;
RightRotation(Node);
end;
Node^.Parent^.Color := node_Black;
Node^.Parent^.Parent^.Color := node_Red;
LeftRotation(Node^.Parent^.Parent);
end;
end
end;
Root^.Color := node_Black;
end;
function RBTree.InsertItem(s: string; node: PTreeNode): PTreeNode;
var
comparison: integer;
GreaterThanLeft, LessThanRight: boolean;
T: PTreeNode;
begin
if root = nil then begin
root := new(PTreeNode, init(s, nil));
root^.Color := node_Black;
InsertItem := root; exit
end;
while True do begin
comparison := compare(s, node^.data_string);
if node^.Deleted then begin
if comparison=0 then begin
node^.Deleted := false;
InsertItem := nil; exit
end;
if node^.Left = nil then GreaterThanLeft := true
else GreaterThanLeft := (compare(s, node^.left^.data_string) > 0);
if node^.Right = nil then LessThanRight := true
else LessThanRight := (compare(s, node^.right^.data_string) > 0);
if GreaterThanLeft and LessThanRight then begin
node^.data_string := s;
node^.Deleted := false;
InsertItem := nil; exit
end;
end;
if comparison < 0 then begin
if Node^.Left = nil then begin
Node^.Left := new(PTreeNode, init(s, Node));
InsertItem := Node^.Left;
exit
end
else Node := Node^.Left;
end
else
if comparison > 0 then begin
if Node^.Right = nil then begin
Node^.Right := new(PTreeNode, init(s, Node));
InsertItem := Node^.Right;
exit
end
else Node := Node^.Right;
end
else
if Node^.Deleted = false then begin
Sound(220);
Delay(1200);
NoSound;
writeln('!!!!!! Такой узел уже есть !!!!!!!');
T := node;
while(T^.Duplicates <> nil) do T := T^.Duplicates;
T^.Duplicates := new(PTreeNode, init(s, T));
InsertItem := nil; exit
end
end;
end;
function RBTree.Remove(s: string): boolean;
var T, prev_node, node: PTreeNode;
begin
Remove := False;
Node := SearchFirstMatch(s);
if node = nil then exit;
if node^.Duplicates <> nil then begin
T := node;
while T^.Duplicates <> nil do begin
prev_node := T;
T := T^.Duplicates;
end;
node^.data_string := T^.data_string;
dispose(T);
prev_node^.Duplicates := nil;
Remove := true;
end
else
Node^.Deleted := true;
Remove := True
end;
function RBTree.Search(s: string): integer;
var
node: PTreeNode;
comparison: integer;
begin
Search := -1;
node := root;
while Node <> nil do begin
comparison := compare(s, node^.data_string);
if comparison < 0 then Node := Node^.Left
else if comparison > 0 then Node := Node^.Right
else if Node^.Deleted then exit
else begin
search := 1; exit
end;
end;
end;
function RBTree.SearchFirstMatch(s: string): PTreeNode;
var
node: PTreeNode;
comparison: integer;
begin
SearchFirstMatch := nil;
node := root;
while Node <> nil do begin
comparison := compare(s, node^.data_string);
if comparison < 0 then Node := Node^.Left
else if comparison > 0 then Node := Node^.Right
else if Node^.Deleted then exit
else begin
SearchFirstMatch := node; exit
end;
end;
end;
procedure RBTree.SaveToFile(var f: text);
begin
SaveNode(0, root, f);
end;
procedure RBTree.SaveNode(level: integer;
const node: PTreeNode; var f: text);
const
_color: array[0 .. 1] of char = ('B', 'R');
begin
if node <> nil then begin
if _color[node^.Color]='B' then TextColor(BLACK)
else TextColor(RED);
if node^.Deleted then TextBackground(BLUE);
write(f, '':3*level,node^.data_string );
TextBackground(WHITE);
TextColor(GREEN);
writeln(f,'');
SaveNode(level + 1, node^.Left, f);
SaveNode(level + 1, node^.Right, f);
end;
end;
function RBTree.LeftDepth: integer;
begin
LeftDepth := TreeDepth(Root^.Left);
end;
function RBTree.RightDepth: integer;
begin
RightDepth := TreeDepth(Root^.Right);}
end;
function RBTree.TreeDepth(p: PTreeNode): integer;
var _left, _right: integer;
begin
_left := 0; _right := 0;
if p^.Left <> nil then _left := TreeDepth(p^.Left);
if p^.Right <> nil then _right := TreeDepth(p^.Right);
if _left > _right then TreeDepth := _left + 1
else TreeDepth := _right + 1;
end;
function RBTree.NumberOfLeaves(p: PTreeNode): integer;
var total: integer;
begin
NumberOfLeaves := 1;
total := 0;
if (p^.Left = nil) and (p^.Right = nil) then exit;
if p^.Left <> nil then inc(total, NumberOfLeaves(p^.Left));
if p^.Right <> nil then inc(total, NumberOfLeaves(p^.Right));
NumberOfLeaves := total;
end;
procedure RBTree.LeftRotation(node: PTreeNode);
var Right: PTreeNode;
begin
Right := node^.Right;
node^.Right := Right^.Left;
if Right^.Left <> nil then
Right^.Left^.Parent := Node;
if Right <> nil then
Right^.Parent := Node^.Parent;
if Node^.Parent <> nil then begin
if Node = Node^.Parent^.Left then Node^.Parent^.Left := Right
else Node^.Parent^.Right := Right;
end
else Root := Right;
Right^.Left := Node;
if Node <> nil then Node^.Parent := Right;
end;
procedure RBTree.RightRotation(node: PTreeNode);
var Left: PTreeNode;
begin
Left := node^.Left;
Node^.Left := Left^.Right;
if Left^.Right <> nil then Left^.Right^.Parent := Node;
if Left <> nil then Left^.Parent := Node^.Parent;
if Node^.Parent <> nil then begin
if Node = Node^.Parent^.Right then Node^.Parent^.Right := Left
else Node^.Parent^.Left := Left;
end
else Root := Left;
Left^.Right := Node;
if Node <> nil then Node^.Parent := Left;
end;
var
console: text;
s: string_20;
tree: RBTree;
begin
assigncrt(console);
rewrite(console);
TextBackground(WHITE);
TextColor(GREEN);
tree.init;
repeat
writeln('1 – Построение дерева');
writeln('2 - Поиск');
writeln('3 – Показ дерева');
writeln('4 – Удаление узла');
writeln('9 - Выход');
readln(s);
if ( s='1') then begin
repeat
write('enter string (20 chars max): '); readln(s);
if s <> '' then begin
tree.insert(s);
Writeln('__________________________________________');
tree.SaveToFile(console); { Выводим дерево на консоль }
writeln('__________________________________________');
end;
until s = '';
end;
if ( s='3') then begin
Writeln('**');
tree.SaveToFile(console);
Writeln('**');
end;
if ( s='4') then begin
write('enter string (20 chars max): '); readln(s);
Write('node ');Write(s);
if tree.search(s)=1 then begin
tree.Remove(s);
writeln(' удалён');
tree.SaveToFile(console);
end
else writeln(' не найден');
Writeln('**');
end;
if ( s='2') then begin
write('enter string (20 chars max): '); readln(s);
Write('node ');Write(s);
if tree.search(s)=1 then writeln(' найден')
else writeln(' не найден');
Writeln('**');
end;
until s = '9';
tree.SaveToFile(console);
{ Проверяем работу Search }
if tree.search('four') = 1 then writeln('found')
else writeln('not found');
{ Проверяем работу Remove }
tree.Remove('four');
tree.SaveToFile(console);
tree.done;
close(console);
end.