WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega 1. ДВОИЧНОЕ ДЕРЕВО. ДВОИЧНОЕ ДЕРЕВО ПОИСКА Двоичное дерево — ...»

Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega

1. ДВОИЧНОЕ ДЕРЕВО. ДВОИЧНОЕ ДЕРЕВО

ПОИСКА

Двоичное дерево — абстрактная структура данных, являющееся программной

реализацией двоичного дерева (графа). Оно состоит из узлов (вершин) - записей вида

(data, l, r), где data — некоторые данные привязанные к узлу, l, r — ссылки на узлы,

являющиеся детьми данного узла. Узел l называется левым ребёнком (сыном), а узел r — правым.

Пример:

Двоичное дерево поиска — это двоичное дерево, в котором данные, привязанные к каждому узлу, представляют собой пару (ключ и значение), причём на ключах определена операция сравнения "меньше", и для всех узлов дерева выполнено свойство, называемое свойством дерева поиска:

у всех узлов левого поддерева произвольного узла n значение ключей меньше, нежели значения ключа узла n, у всех узлов правого поддерева произвольного узла n значение ключей не меньше, нежели значения ключа узла n.

Основное назначение двоичных деревьев заключается в повышении эффективности поиска.

Пример:

Aleksei Tepljakov 1 03.06.2009 Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega

2. AVL-ДЕРЕВО AVL-дерево – балансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. Поиск, добавление и удаление элемента занимают O(log n) времени в среднем и худшем случаях. Операции добавления и удаления могут привести к необходимости перебалансировать дерево.



Балансным фактором вершины является высота правого поддерева минус высота левого поддерева. Вершина с балансным фактором 1, 0 или -1 считается сбалансированной.

Любое другое значение фактора означает, что необходимо осуществить перебалансировку дерева.

Правила ротации:

При помощи правил ротации можно сбалансировать AVL-дерево.

Пример:

Aleksei Tepljakov 2 03.06.2009 Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega

3. SPLAY ДЕРЕВО Splay дерево — самобалансирующееся двоичное дерево поиска с дополнительным свойством, которое заключается в том, что наиболее часто используемые элементы доступны вновь для быстрого использования. Операции выполняются за время O(log n).

Все стандартные операции сопровождаются сплееровнием (в переводе — скашиванием или расширением — требуется специальный перевод), суть которого в том, что определённый элемент по правилам ротации помещается на место вершины.

В конечном итоге, наиболее часто используемые элементы дерева оказываются близко к вершине, что во много раз ускоряет их нахождение. Поскольку сплей-деревья достаточно легко реализуются, во многих случаях их использование более приоритетно, чем использование АВЛ-деревьев или Красно-Чёрных деревьев. Сплей-деревья нашли применение в таких алгоритмах, как кэширование и сбор мусора (garbage collection).

4. B-ДЕРЕВО, B* ДЕРЕВО, B+ ДЕРЕВО

В-деревом порядка m называется дерево, обладающее следующими свойствами:

каждая вершина имеет не более m потомков;

каждая вершина, кроме корня и листьев, имеет не менее m/2 потомков ;

невесячая вершина с k потомками содержит k-1 ячеек информации;

корень, если он не является листом, имеет не менее 2 потомков;

все листья расположены на одном уровне и не содержат информации.

B-деревья используются, в основном, при реализации файловых систем и баз данных.

В стандартных B-деревьях ключи и данные хранятся как во внутренних узлах, так и в листьях (концевых узлах). Если при спуске по дереву во время вставки встречен заполненный узел, его содержимое перераспределяется между братьями. Если братья тоже полны, создается новый узел и половина ключей потомка пересылается в него.

Пример B-дерева:

B* дерево — деревья устроены аналогично обычным B-деревьям, единственное отличие узлы заполняются на 2/3. Это приводит к лучшему использованию места, занимаемого деревом, и чуть лучшей производительности.

Aleksei Tepljakov 3 03.06.2009 Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega B+ дерево — все ключи такого хранятся в листьях, там же хранится и информационная часть узла. Во внутренних узлах хранятся копии ключей — они помогают искать нужный лист. У указателей смысл иной, чем при работе с обычными B-деревьями: левый указатель ведет к ключам, которые меньше заданного значения, правый - ключам, которые больше или равны.

5. RED-BLACK ДЕРЕВО

Красно-черное дерево - это бинарное дерево с следующими свойствами:

Каждый узел покрашен либо в черный, либо в красный цвет;

Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели);

Листья покрашены в черный цвет;

Если узел красный, то оба его потомка черны;

На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Пример:

Наиболее важным свойством RB-деревьев является то, что самый длинный путь от корня до одного из листьев длиннее самого короткого пути не более чем в два раза.

–  –  –

6. ДИГИТАЛЬНОЕ ДЕРЕВО ПОИСКА

В каждой вершине такого дерева хранится полный ключ, но переход по левой или правой ветви происходит не путем сравнения ключа-аргумента со значением ключа, хранящегося в вершине, а на основе значения очередного бита аргумента.

Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 - по правой.

Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется следующий бит аргумента и т.д., пока либо не будут проверены все биты аргумента, или мы не попадём на вершину с отсутствующей левой или правой ссылкой.

Пример:

7. TRIE ДЕРЕВО TRIE дерево —структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от бинарных деревьев, в листьях дерева не хранится ключ. Значение ключа можно получить просмотром всех родительских узлов, каждый из которых хранит один или несколько символов алфавита. Корень дерева связан с пустой строкой.

Таким образом, потомки узла имеют общий префикс, откуда и произошло название данного АТД. Значения, связанные с ключем, обычно не связаны с каждым узлом, а только с листьями и, возможно, некоторыми внутренними узлами.

–  –  –

8. ТРОЙНОЕ (TERNARY) ДЕРЕВО Ternary search дерево — это структура данных, комбинирующая в себе эффективность по времени, присущую дигитальным деревьям с пространственной эффективностью двоичных деревьев поиска. Полученная таким образом структура данных быстрее хеширования для решения большого числа проблем поиска и может разрешить большее количество проблем.

Обычно тройные деревья содержат строки символов. Пример:

–  –  –

9. КУЧА (HEAP) Кучей называется структура данных, представляющая собой дерево, которая характеризуется свойством кучи: если Б является дочерней вершиной А, то ключ при А больше или равен ключу при Б. Отсюда вытекает, что элемент с наибольшим ключом всегда является корнем.

Кучи используются для реализации очередей с приоритетами. Эффективность операций с кучами имеет огромное значение в некоторых алгоритмах с использованием графов.

Типичные операции:

Удаление максимального (или минимального — в зависимости от типа кучи) элемента;

Обновление ключа;

Вставка ключа;

Соединение двух куч.

Кучи используются, например, в сортировке кучами (heapsort).

Пример:

10. LEFTIST ДЕРЕВО Рангом бинарного дерева T назовем длину правого пути от корня до листа и будем обозначать как rank(T).

Назовем бинарное дерево Leftist, если для каждого его поддерева T выполняется Leftist условие:





rank(left(T)) = rank(right(T)) Бинарное дерево с вышеприведенными операциями является Leftist кучей, если оно удовлетворяет свойству кучи и Leftist условию.

–  –  –

11. БИНОМИАЛЬНОЕ ДЕРЕВО И

БИНОМИАЛЬНАЯ КУЧА

Биномиальными деревьями называются деревья с порядком на детях B0, B1, B2, …, определяемые индуктивно.

Дерево В0 состоит из единственной вершины.Дерево Bk склеено из двух экземпляров дерева Bk-1: корень одного из них объявлен самым левым ребёнком корня другого.

Лемма (свойства биномиальных деревьев). Дерево Bk:

–  –  –

Следствие. Максимальная степень вершины в биномиальном дереве с n вершинами равна log n.

Aleksei Tepljakov 8 03.06.2009 Algoritmid ja Andmestruktuurid Teooria — puud ja mned operatsioonid nendega Биномиальная куча— это набор Н биномиальных деревьев, в вершинах которых записаны ключи и, возможно, дополнительная информация.

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

–  –  –

Первое свойство гарантирует, что корень каждого из деревьев имеет наименьший ключ среди его вершин.

Из второго свойства следует, что суммарное количество вершин в биномиальной куче Н однозначно определяет размеры входящих в неё деревьев. В самом деле, общее число вершин, равное n, есть сумма размеров отдельных деревьев, которые суть различные степени двойки, а такое представление единственно (двоичная система счисления).

Отсюда вытекает также, что куча с n элементами состоит из не более чем [log n]+1 биномиальных деревьев.

Похожие работы:

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "ГОСУДАРСТВЕННОЕ УЧИЛИЩЕ (КОЛЛЕДЖ) ОЛИМПИЙСКОГО РЕЗЕРВА г. ИРКУТСКА" РАБОЧАЯ ПРОГРАММА ДОПОЛНИТЕЛЬНОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ по дисциплине "ОСНОВЫ ВРАЧЕБНОГО КОНТРОЛЯ" Форма обучения: заочная Иркутск 20...»

«ОБЪЯВЛЕНИЕ ОБ ЭЛЕКТРОННЫХ ЗАКУПКАХ СПОСОБОМ ЗАПРОС ЦЕНОВЫХ ПРЕДЛОЖЕНИЙ N:161238 1. в лице "Актюбинские МЭС" (наименование заказчика) объявляет о проведении электронных закупок способом запроса ценовых предложений Поздравления юбиляров, дни рождения и др. (на...»

«АНТ И В И РУС НА Я СИ СТ Е М А ЗА Щ И Т Ы ПР Е ДПР И Я ТИ Я Содержание Современные вирусные угрозы Информационные ресурсы о современных вирусных угрозах Пути проникновения вирусных угроз в корпоративные сети Требования законодательства Российской Федерации в области антивирусной защиты. 14 Требования к организации антивирусной системы защиты лок...»

«ПРОСПЕКТ ТРЕТЬЕГО ВЫПУСКА ОБЛИГАЦИЙ В ПРЕДЕЛАХ ТРЕТЬЕЙ ОБЛИГАЦИОННОЙ ПРОГРАММЫ АКЦИОНЕРНОГО ОБЩЕСТВА "КАЗАХСТАНСКАЯ ИПОТЕЧНАЯ КОМПАНИЯ" (АО "КАЗАХСТАНСКАЯ ИПОТЕЧНАЯ КОМПАНИЯ") Республика Казахстан, г. Алматы, 2007 год 1. Настоящий выпуск облигаций осуществляется в соответствии с проспектом третьей облигационной про...»

«Установка Использование и обслуживание Товарный знак © 2008. Все права сохранены. Никакая часть этого документа не может быть воспроизведена без разрешения. Все товарные знаки и торговые марки, упоми...»

«МИНИСТЕРСТВО ИНОСТРАННЫ Х Д Е Л СССР ДОКУМЕНТЫ ВНЕШНЕЙ ПОЛИТИКИ СССР ИЗДАТЕЛЬСТВО ПОЛИТИЧЕСКОМ ЛИТЕРАТУРЫ М о с к в а • 19 6 7 9(С}2 Д63 комиссия ПО ИЗДАНИЮ ДИПЛОМАТИЧЕСКИХ ДОКУМЕНТОВ ПРИ МИД СССР: д-р з ко ко м. наук Л. Л. ГРОМЫКО (Председат...»

«Всероссийская олимпиада школьников по основам безопасности жизнедеятельности. Школьный этап. (10-11 классы) № ОУ_. Фамилия, имя, отчество1. ТЕОРЕТИЧЕСКИЙ ТУР Задание 1. Вы должны перейти дорогу. Подумайте и ответьте, в чем опасность приближающей...»

«Министерство образования и науки Российской Федерации НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНДИВИДУАЛЬНЫЙ ПРИКЛАДНОЙ ПРОЕКТ Тема проекта: "Энергосервисный договор (контракт). Заключение энергосервисного договора в г.Сосновоборске" Выполнил: Иванова Алена Александровна, гл...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.