Без темы
<<  Auditting iPhone and iPad applications B?ume im Winter  >>
Augmenting Data Structures, Dynamic Order Statistics
Augmenting Data Structures, Dynamic Order Statistics
Содержание
Содержание
Красно-черные деревья
Красно-черные деревья
Красно-черные деревья
Красно-черные деревья
Красно-черные деревья
Красно-черные деревья
Повороты
Повороты
Алгоритм вставки
Алгоритм вставки
Алгоритм вставки
Алгоритм вставки
Алгоритм вставки
Алгоритм вставки
Алгоритм удаления
Алгоритм удаления
Алгоритм удаления
Алгоритм удаления
Алгоритм удаления
Алгоритм удаления
Применение
Применение
Динамические порядковые статистики
Динамические порядковые статистики
Дерево порядковой статистики – пример*
Дерево порядковой статистики – пример*
Выборка элемента с заданным рангом
Выборка элемента с заданным рангом
Выборка элемента с заданным рангом - пример
Выборка элемента с заданным рангом - пример
Определение ранга элемента
Определение ранга элемента
Определение ранга элемента - пример
Определение ранга элемента - пример
Поддержка размера поддеревьев
Поддержка размера поддеревьев
Расширение структур данных
Расширение структур данных
Расширение структур данных – теорема
Расширение структур данных – теорема
Сравнение с AVL-деревьями
Сравнение с AVL-деревьями
График производительности
График производительности
График производительности
График производительности
Список литературы
Список литературы

Презентация: «Augmenting Data Structures, Dynamic Order Statistics». Автор: ta. Файл: «Augmenting Data Structures, Dynamic Order Statistics.pptx». Размер zip-архива: 804 КБ.

Augmenting Data Structures, Dynamic Order Statistics

содержание презентации «Augmenting Data Structures, Dynamic Order Statistics.pptx»
СлайдТекст
1 Augmenting Data Structures, Dynamic Order Statistics

Augmenting Data Structures, Dynamic Order Statistics

Клишин Алексей, 86м22 Линева Татьяна, 85м1 Макарова Татьяна, 85м1

2 Содержание

Содержание

Красно-черные деревья Определение, пример Основные операции Повороты Алгоритмы Динамические порядковые статистики Выборка элемента с заданным рангом Определение ранга элемента Поддержка размера поддеревьев Сравнение с AVL-деревьями Применение

2

3 Красно-черные деревья

Красно-черные деревья

Свойства: Каждый узел дерева является красным или черным; Если узел красный, то оба дочерних узла черные; Для каждого узла все пути от него до листьев, являющихся потомками данного узла содержат одно и то же количество черных узлов. Корень дерева всегда чёрный; Каждый лист дерева является черным.

3

4 Красно-черные деревья

Красно-черные деревья

Пример

Каждый узел дерева содержит поля color, key, left, right и p.

4

5 Красно-черные деревья

Красно-черные деревья

Основные операции

Лемма: красно-черное дерево с n внутренними узлами имеет высоту не более, чем 2lg(n + 1).

Вставка элемента(RB_INSERT, RB_INSERT_FIXUP) Удаление элемента(RB_DELETE, RB_DELETE_FIXUP) Вспомогательная операция – повороты(LEFT_ROTATION, RIGHT_ROTATION) Вставка, удаление – O(h), повороты – O(1), где h – высота дерева

5

6 Повороты

Повороты

6

LEFT_ROTATE(T, x) y = right[x] устанавливаем y right [x] = left [y] левое поддерево y становится правым поддеревом x if left [y] ? nil[t] then p[left [y]] = x p[y] = p[x] перенос родителя x в y if p[x] = nil[t] then root[t] = y else if x = left[p[x]] then left[p[x]] = y else right[p[x]] = y left [y] = x x – левый дочерний y p[x] = y

7 Алгоритм вставки

Алгоритм вставки

7

RB_INSERT(T, z) y = nil[T] x = root [T] while x ? nil[T] do y = x if key [z] < key [x] if y = nil [T] then x = left [x] else x = right [x] p[x] = y then root [T] = z else if key [z] < key [y] then left [y] = z else right [y] = z left [z] = nil [T] right [z] = nil [T] color [z] = RED RB_INSERT_FIXUP(T, z)

8 Алгоритм вставки

Алгоритм вставки

8

RB_INSERT_FIXUP(T, z) while color [p[z]] = RED do if p[z] = left [p[p[z]]] then y = right [p[p[z]]] if color [y] = RED then color [p[z]] = BLACK 1 color [y] = BLACK 1 color [p[p[z]]] = RED 1 z = p[p[z]] 1 else if z = right [p[z]] then z = p[z] 2 LEFT_ROTATE(T, z) 2 color [p[z]] = BLACK 3 color [p[p[z]]] = RED 3 RIGHT_ROTATE(T, p[p[z]]) 3 else (то же, что и в “then”, с заменой left на right и наоборот) color [root[t]] = BLACK

Красный предок, красный "дядя"

9 Алгоритм вставки

Алгоритм вставки

9

RB_INSERT_FIXUP(T, z) while color [p[z]] = RED do if p[z] = left [p[p[z]]] then y = right [p[p[z]]] if color [y] = RED then color [p[z]] = BLACK 1 color [y] = BLACK 1 color [p[p[z]]] = RED 1 z = p[p[z]] 1 else if z = right [p[z]] then z = p[z] 2 LEFT_ROTATE(T, z) 2 color [p[z]] = BLACK 3 color [p[p[z]]] = RED 3 RIGHT_ROTATE(T, p[p[z]]) 3 else (то же, что и в “then”, с заменой left на right и наоборот) color [root[t]] = BLACK

Красный предок, черный"дядя"

10 Алгоритм удаления

Алгоритм удаления

10

11 Алгоритм удаления

Алгоритм удаления

11

Если брат этого ребёнка удаленной вершины красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет

2. Если брат текущей вершины был чёрным, то получаем три случая: Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины

12 Алгоритм удаления

Алгоритм удаления

12

Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение RIGHT_ROTATE(T, b)

Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение LEFT_ROTATE(T, a) и выходим из алгоритма

13 Применение

Применение

13

Красно-черные деревья используются в ядре Linux: Планировщики ввода-вывода; deadline (алгоритм крайнего срока) и CFQ (completely fair queuing - абсолютно честная очередь) используют красно-чёрные деревья для отслеживания запросов; драйвер пакетной записи CD/DVD использует красно-чёрные деревья для этих же целей; Код таймеров высокого разрешения использует красно-чёрное дерево для упорядочивания невыполненных запросов на таймеры. Файловая система ext3 отслеживает в красно-чёрных деревьях содержимое (записи) директорий; Отслеживаю тся диапазоны виртуальных адресов (VMAs), дескрипторы файлов, на которых применяется опрос вызовом epoll(), криптографические ключи и сетевые пакеты в планировщике "hierarchical token bucket" (классовая дисциплина очереди НТВ)

14 Динамические порядковые статистики

Динамические порядковые статистики

i-ой порядковой статистикой множества из n элементов (i ? {1, 2, … , n}) является элемент множества с i-ым в порядке возрастания ключом Ранг элемента – его порядковый номер в линейно упорядоченном множестве Дерево порядковой статистики (order-statistic tree) - красно-чёрное дерево T, каждая вершина x которого, помимо обычных полей key[x], color[x], p[x], left[x] и right[x], имеет поле size[x] size[nil] = 0 size[x] = size[left[x]] + size[right[x]] + 1

14

15 Дерево порядковой статистики – пример*

Дерево порядковой статистики – пример*

15

* Рис. 14.1 из [1]

16 Выборка элемента с заданным рангом

Выборка элемента с заданным рангом

16

OS_SELECT(x, i) r = size[left[x]] + 1 if i = r then return x else if i < r then return OS_SELECT(left [x], i) else return OS_SELECT(right[x], i - r)

Время работы процедуры OS_SELECT в динамическом множестве из n элементов равно O(lg n)

17 Выборка элемента с заданным рангом - пример

Выборка элемента с заданным рангом - пример

17

18 Определение ранга элемента

Определение ранга элемента

18

OS_RANK(T, x) r = size[left[x]] + 1 y = x while y ? root[T] do if y = right[p[y]] then r = r + size[left[p[y]]] + 1 y = p[y] return r

Время работы процедуры OS_RANK в динамическом множестве из n элементов равно O(lg n)

19 Определение ранга элемента - пример

Определение ранга элемента - пример

19

20 Поддержка размера поддеревьев

Поддержка размера поддеревьев

20

LEFT_ROTATE(T, x) … 13) size[y] = size[x] 14) size[x] = size[left[x]] + size[right[x]] + 1

21 Расширение структур данных

Расширение структур данных

21

Выбор базовой структуры данных Определение необходимой дополнительной информации, которую следует хранить в базовой структуре данных и поддерживать ее актуальность Проверка того, что дополнительная информация может поддерживаться основными модифицирующими операциями над базовой структурой данных 4. Разработка новых операций

22 Расширение структур данных – теорема

Расширение структур данных – теорема

22

Теорема. Пусть f – поле, которое расширяет красно - черное дерево T из n узлов, и пусть содержимое поля f узла х может быть вычислено с использованием лишь информации, хранящейся в узлах х, left[x], right[x], включая f[left[x]] и f[rigth[x]]. Тогда мы можем поддерживать актуальность информации f во всех узлах дерева T в процессе вставки и удаления без влияния на асимптотическое время работы данных процедур O(lg n).

23 Сравнение с AVL-деревьями

Сравнение с AVL-деревьями

23

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. Общее: Время вставки и удаления O(lg n) Для модификации обоих типов деревьев требуется выполнение дополнительных ротаций. Разное: Когда общее число узлов дерева одинаково, максимальная высота AVL- дерева всегда будет меньше 2. Для хранения красно-черного дерева требуется меньше памяти

24 График производительности

График производительности

Вставка элемента

24

Intel Core i5-2520M CPU 2.50 Ghz 8.00 GB Ram, Win7 x64

25 График производительности

График производительности

Удаление элемента

25

Intel Core i5-2520M CPU 2.50 Ghz 8.00 GB Ram, Win7 x64

26 Список литературы

Список литературы

26

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2002. Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees // MITOPENCOURSEWARE Massachusetts Institute Of Technology. – URL: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-11-augmenting-data-structures-dynamic-order-statistics-interval-trees/ Работа со структурами данных в языках Си и Python: Часть 9. Красно-черные деревья // IBM. – URL: http://www.ibm.com/developerworks/ru/library/l-data_structures_09/ Красно-чёрные деревья (Red black trees) в ядре Linux//rfLinux. – URL: http://rflinux.blogspot.com/2011/10/red-black-trees-linux_16.html

«Augmenting Data Structures, Dynamic Order Statistics»
http://900igr.net/prezentacija/anglijskij-jazyk/augmenting-data-structures-dynamic-order-statistics-87161.html
cсылка на страницу
Урок

Английский язык

29 тем
Слайды
900igr.net > Презентации по английскому языку > Без темы > Augmenting Data Structures, Dynamic Order Statistics