Презентация АА-деревья. Операции для работы с АА-деревом и алгоритмы их реализации онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему АА-деревья. Операции для работы с АА-деревом и алгоритмы их реализации абсолютно бесплатно. Урок-презентация на эту тему содержит всего 48 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » АА-деревья. Операции для работы с АА-деревом и алгоритмы их реализации
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:48 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:231.31 kB
- Просмотров:86
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
Содержание слайда: Содержание
Определение структуры
Связь АА-деревьев с другими деревьями поиска
История структуры
Свойства АА-деревьев
Основные операции для работы с АА-деревом и алгоритмы их реализации :
Операция “skew”
Операция “split”
Вставка в АА-дерево
Удаление из АА-дерева
Список используемой литературы и источников
№3 слайд
Содержание слайда: Определение структуры
АА-дерево – это форма сбалансированного дерева, которое используется для хранения и эффективного извлечения упорядоченных данных. АА-деревья названы по имени их изобретателя Арне Андерссона (Arne Andersson).
АА-дерево является разновидностью красно-черного дерева, но в отличие от красно-черных деревьев, красные узлы на АА-дереве могут быть добавлены только как правый потомок, благодаря этому, АА-деревья обладают повышенной простотой кодирования.
№4 слайд
Содержание слайда: Связь АА-деревьев с красно-черными и
2-3 деревьями
Физически, красно-черное дерево похоже на 2-3 дерево (обычное бинарное дерево поиска, где некоторые узлы имеют две ссылки, а некоторые узлы группируются в пары и пара содержит три ссылки) (рис. 1) с дополнительными ограничениями. Если представлять узел с двумя ключами в виде двух отдельных узлов, и красить все одиночные узлы и «левые половины» двойных узлов в черный цвет, а «правые половины» в красный, то мы получим обычное красно-черное дерево, в котором все красные вершины являются правыми потомками черных (рис. 2).
№5 слайд
Содержание слайда: Связь АА-деревьев с красно-черными и
2-3 деревьями
Возвращаясь к АА-деревьям, вместо того, чтобы раскрашивать узлы в красный и черный цвета, введем понятие уровень узла (level). Будем считать, что все листья дерева имеют уровень 1 (единица), а уровень родителя имеет уровень на единицу больший, чем уровень потомка. Красные узлы находятся на уровне своих родителей. То есть, в качестве исключения будем считать, что если потомок является правым потомком, то его уровень может быть равен уровню родительского узла (рис. 3).
№7 слайд
Содержание слайда: История структуры
AA-дерево было придумано Арне Андерссоном в 1993 году, который первым решил, что для упрощения балансировки дерева нужно ввести понятие уровень (level) вершины. Если представить себе дерево растущим сверху вниз от корня (то есть «стоящим на листьях»), то уровень любой листовой вершины будет равен 1. В своей работе Арне Андерссон приводит простое правило, которому должно удовлетворять AA-дерево:
К одной вершине можно присоединить другую вершину того же уровня, но только одну и только справа (одна правая одноуровневая связь).
№10 слайд
Содержание слайда: ОСНОВНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ С АА-ДЕРЕВОМ И АЛГОРИТМЫ ИХ РЕАЛИЗАЦИИ
Для балансировки АА-дерева нужно всего 2 (две) различных операции. Нетрудно их понять из правила «одна правая одноуровневая связь» : это устранение левой связи на одном уровне и устранение двух правых связей на одном уровне.
Эти операции в оригинальной работе Арне Андерссона названы “skew”(«перекос») и “split”(«расщепление») соответственно.
№11 слайд
Содержание слайда: “skew” устранение левой связи на одном уровне
Данная операция устраняет горизонтальную левую связь при помощи вращения узла вправо каждый раз, когда горизонтальная левая связь найдена.
На рисунке горизонтальная стрелка обозначает связь между вершинами одного уровня, а наклонная (вертикальная) — между вершинами разного уровня
№12 слайд
Содержание слайда: Код процедуры “skew”
procedure Skew_t (var t : pl_tree);
var
tmp : pl_tree;
begin
if t <> nil then
begin
if t^.left <> nil then
begin
if t^.left^.level = t^.level then
begin {rotate right}
tmp := t;
t := tmp^.left;
tmp^.left := t^.right;
t^.right := tmp;
end;
end;
end;
end;
№14 слайд
Содержание слайда: Код процедуры “split”
procedure Split_t (var t : pl_tree);
var
tmp : pl_tree;
begin
if t <> nil then
begin
if t^.right <> nil then
begin
if t^.right^.right <> nil then
begin
if t^.right^.right^.level = t^.level then
begin {rotate left}
tmp :=t;
t := tmp^.right;
tmp^.right := t^.left;
t^.left := tmp;
Inc (t^.level);
end;
end;
end;
end;
end;
№15 слайд
Содержание слайда: Алгоритм вставки
Добавляем новый узел на 1(первый) уровень;
Вызываем операцию “skew”;
Вызываем операцию “split”.
Вставка узла может:
Не нарушить правило построения АА-дерева, например ;
Нарушить правило «левого потомка», например Исправление может быть сделано простым поворотом “skew”;
Нарушить правило «двух правых потомков» , например . Исправление может быть сделано расщеплением “split”;
Вставка узла может повлечь за собой серию поворотов и расщеплений, например .
№16 слайд
Содержание слайда: Вставка элемента в дерево
procedure Insert_Node (var root_f : pl_tree; x : integer);
begin
if root_f = nil then
begin
new (root_f);
root_f^.left := nil;
root_f^.right := nil;
root_f^.key := x;
root_f^.level := 1;
end else
begin
if root_f^.key > x then
Insert_Node (root_f^.left,x)
else if root_f^.key < x then
Insert_Node (root_f^.right,x);
end;
Skew_t (root_f);
Split_t (root_f);
end;
№30 слайд
Содержание слайда: Удаление элемента
procedure Delete_Node (var root_f : pl_tree; newkey : integer);
begin
if root_f <> nil then
begin
// 1. спускаемся вниз и запоминаем last и deleted
last := root_f;
if newkey < root_f^.key then
Delete_Node (root_f^.left, newkey)
else
begin
deleted := root_f;
Delete_Node (root_f^.right, newkey);
end;
// 2. удаляем элемент, если найден
if (root_f = last) and (deleted <> nil) and (newkey = deleted^.key)
then
begin
deleted^.key := root_f^.key;
deleted := nil;
root_f := root_f^.right;
dispose (last);
end
else if (Get_Level(root_f^.left) < (Get_Level(root_f) - 1)) or
(Get_Level(root_f^.right) < (Get_Level(root_f) - 1)) then
begin
// 3. выполняем балансировку при движении вверх
Dec (root_f^.level);
if root_f^.right^.level > root_f^.level then
root_f^.right^.level := root_f^.level;
Skew_t (root_f);
Skew_t (root_f^.right);
Skew_t (root_f^.right^.right);
Split_t (root_f);
Split_t (root_f^.right);
end;
end;
end;
№46 слайд
Содержание слайда: Заключение
В своей работе Арне Андерссон делает вывод, что если сравнивать по производительности четыре типа двоичных деревьев поиска, а именно:
АВЛ-дерево;
красно-черное дерево;
2-3-дерево;
АА-дерево,
то можно сделать вывод, что сбалансированность (и скорость поиска) лучше всего у АВЛ-дерева, чуть хуже у красно-черного дерева, и еще чуть хуже у 2-3-дерева и эквивалентного ему по структуре АА-дерева.
Алгоритмы балансировки очень сложны для АВЛ-дерева и 2-3-дерева, поэтому на практике предпочитают использовать красно-черные и АА-деревья. Самые простые алгоритмы вставки и удаления узлов у АА-дерева, однако, если вставка и удаление элементов встречаются гораздо реже, чем поиск, то красно-черные деревья будут предпочтительнее .
Преимуществом АА-дерева по сравнению с красно-черным деревом является то, что алгоритмы, используемые при вставке и удалении узла в АА-дереве, а также балансировка дерева существенно проще, чем в красно-черном дереве.
№47 слайд
Содержание слайда: СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ И ИСТОЧНИКОВ
AA-Tree – http://en.wikipedia.org/wiki/AA_tree.
AA-Tree или простое бинарное дерево – http://habrahabr.ru/post/110212 .
АА-дерево – http://www.proteus2001.narod.ru/gen/txt/8/aa.html.
A. Andersson. Balanced search trees made simple. Algorithms and Data Structures, pages 60-71, 1993 .
Сайт А.А.Кубенского для студентов ИТМО. Алгоритмы и структуры данных. Презентация лекции по 2-3 деревьям и АА-деревьям https://drive.google.com/file/d/0BFHfoLzonFRMVoxb1d1RXBSblU/view?pref=2&pli=1 .
David Babcock. York College of Pennsylvania. CS 350 : Data Structures AA Trees .
The European Journal for the Informatics Professional UPGRADE http://www.upgrade-cepis.org Vol. V, No. 5, October 2004 .
Скачать все slide презентации АА-деревья. Операции для работы с АА-деревом и алгоритмы их реализации одним архивом:
-
Операции для работы с файлами
-
Разработка и реализация алгоритма создания и балансировки двоичного дерева поиска со взвешенными узлами
-
Программирование циклических алгоритмов. Операции с памятью. Обработка структур данных (массивов)
-
Разработка приложения Windows Forms на PascalABC для расчета стоимости товара и использование структуры алгоритма расчета
-
Разработка обучающей системы, демонстрирующей работу алгоритмов распределения процессорного времени в операционных системах
-
MPI. Разработка параллельного алгоритма c использованием коллективных операций
-
Аттестационная работа. Образовательная программа элективного курса для 10 класса «Алгоритмизация и программирование»
-
Программа-эмулятор для реализации алгоритма Маркова
-
Разработка информационного портала для реализации электронной техники с возможностью редактирования контента пользователями
-
Операционные системы. API для работы с файлами, каталогами и ФС