Augmenting Data Structures, Dynamic Order Statistics

Augmenting Data Structures, Dynamic Order Statistics

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

Содержание

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

2

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

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

3

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

Пример

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

4

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

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

Лемма: красно-черное дерево с 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

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

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

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

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

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

11

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

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

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

12

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

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

Применение

13

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

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

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

* Рис. 14.1 из [1]

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

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

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

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

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

20

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

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

21

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

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

22

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

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

23

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

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

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

24

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

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

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

25

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

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

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