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

Содержание 2 I.Красно-черные деревья 1. Определение, пример 2. Основные операции 3. Повороты 4.Алгоритмы II.Динамические порядковые статистики 1.Выборка элемента с заданным рангом 2.Определение ранга элемента 3.Поддержка размера поддеревьев III.Сравнение с AVL-деревьями IV. Применение

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

4 Красно-черные деревья. Пример Каждый узел дерева содержит поля color, key, left, right и p.

5 Красно-черные деревья. Основные операции Вставка элемента(RB_INSERT, RB_INSERT_FIXUP) Удаление элемента(RB_DELETE, RB_DELETE_FIXUP) Вспомогательная операция – повороты(LEFT_ROTATION, RIGHT_ROTATION) Вставка, удаление – O(h), повороты – O(1), где h – высота дерева Лемма: красно-черное дерево с n внутренними узлами имеет высоту не более, чем 2lg(n + 1).

Повороты 6 LEFT_ROTATE(T, x) 1)y = right[x] устанавливаем y 2)right [x] = left [y] левое поддерево y становится правым поддеревом x 3) if left [y] nil[T] 4) then p[left [y]] = x 5)p[y] = p[x] перенос родителя x в y 6) if p[x] = nil[T] 7) then root[T] = y 8) else if x = left[p[x]] 9) then left[p[x]] = y 10) else right[p[x]] = y 11) left [y] = x x – левый дочерний y 12) p[x] = y

Алгоритм вставки 7 RB_INSERT(T, z) 1)y = nil[T] 2)x = root [T] 3) while x nil[T] 4) do y = x 5) if key [z] < key [x] 6) if y = nil [T] 7) then x = left [x] 8) else x = right [x] 9)p[x] = y 10) then root [T] = z 11) else if key [z] < key [y] 12) then left [y] = z 13) else right [y] = z 14) left [z] = nil [T] 15) right [z] = nil [T] 16) color [z] = RED 17) RB_INSERT_FIXUP(T, z)

Алгоритм вставки 8 RB_INSERT_FIXUP(T, z) 1) while color [p[z]] = RED 2) do if p[z] = left [p[p[z]]] 3) then y = right [p[p[z]]] 4) if color [y] = RED 5) then color [p[z]] = BLACK 1 6) color [y] = BLACK 1 7) color [p[p[z]]] = RED 1 8) z = p[p[z]] 1 9) else if z = right [p[z]] 10) then z = p[z] 2 11) LEFT_ROTATE(T, z) 2 12) color [p[z]] = BLACK 3 13) color [p[p[z]]] = RED 3 14) RIGHT_ROTATE(T, p[p[z]]) 3 15) else (то же, что и в then, с заменой left на right и наоборот) 16) color [root[T]] = BLACK Красный предок, красный "дядя"

Алгоритм вставки 9 RB_INSERT_FIXUP(T, z) 1) while color [p[z]] = RED 2) do if p[z] = left [p[p[z]]] 3) then y = right [p[p[z]]] 4) if color [y] = RED 5) then color [p[z]] = BLACK 1 6) color [y] = BLACK 1 7) color [p[p[z]]] = RED 1 8) z = p[p[z]] 1 9) else if z = right [p[z]] 10) then z = p[z] 2 11) LEFT_ROTATE(T, z) 2 12) color [p[z]] = BLACK 3 13) color [p[p[z]]] = RED 3 14) RIGHT_ROTATE(T, p[p[z]]) 3 15) else (то же, что и в then, с заменой left на right и наоборот) 16) color [root[T]] = BLACK Красный предок, черный"дядя"

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

11 Алгоритм удаления 1.Если брат этого ребёнка удаленной вершины красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет 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" (классовая дисциплина очереди НТВ)

Динамические порядковые статистики 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

Дерево порядковой статистики – пример* 15 * Рис из [1]

Выборка элемента с заданным рангом 16 OS_SELECT(x, i) 1)r = size[left[x]] + 1 2) if i = r 3) then return x 4) else if i < r 5) then return OS_SELECT(left [x], i) 6) else return OS_SELECT(right[x], i - r) Время работы процедуры OS_SELECT в динамическом множестве из n элементов равно O(lg n)

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

Определение ранга элемента 18 OS_RANK(T, x) 1)r = size[left[x]] + 1 2)y = x 3) while y root[T] 4) do if y = right[p[y]] 5) then r = r + size[left[p[y]]] + 1 6) y = p[y] 7) 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 1.Выбор базовой структуры данных 2.Определение необходимой дополнительной информации, которую следует хранить в базовой структуре данных и поддерживать ее актуальность 3.Проверка того, что дополнительная информация может поддерживаться основными модифицирующими операциями над базовой структурой данных 4. Разработка новых операций

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

Сравнение с AVL-деревьями 23 АВЛ-дерево сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. Общее: 1.Время вставки и удаления O(lg n) 2.Для модификации обоих типов деревьев требуется выполнение дополнительных ротаций. Разное: 1.Когда общее число узлов дерева одинаково, максимальная высота 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 1.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees // MITOPENCOURSEWARE Massachusetts Institute Of Technology. – URL: and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall- 2005/video-lectures/lecture-11-augmenting-data-structures-dynamic- order-statistics-interval-trees/ 3.Работа со структурами данных в языках Си и Python: Часть 9. Красно-черные деревья // IBM. – URL: 4. Красно-чёрные деревья (Red black trees) в ядре Linux//rfLinux. – URL: linux_16.html