Rank-Balanced Trees Локис Василий КН-301 Екатеринбург, 2010

Binary Trees Операции над элементами в деревьях: - поиск - вставка - удаление

Binary Trees Основная проблема в бинарных деревьях поиска (BST) – несбалансированность a b c d e f Поиск ~ O(n) Вставка ~ O(n) Удаление ~ O(n) Хочется, чтобы дерево было всегда идеально сбалансированным c b d e fa Поиск ~ O(log n) Вставка ~ O(log n) Удаление ~ O(log n)

Binary Trees Решение: 1)Хранить в каждой вершине информацию о сбалансированности ее поддеревьев 2)После каждой вставки или удаления, если это необходимо, изменять структуру дерева так, чтобы восстановить баланс. Далее пробегать по дереву и обновлять информацию о сбалансированности Вопрос: Как быстро и безопасно изменять структуру дерева?

Повороты Одинарные левый и правый повороты: сохраняют симметрический порядок; изменяют высоту; работают за O(1).

Повороты Пример двойного правого поворота (двойной левый точно так же только симметрично)

Повороты

Balanced Search Trees Red-Black trees AVL trees Weight Balanced trees LLRB trees 2,3 trees B trees BinaryMultiway

Red-Black Trees Красно-черное дерево – самобалансирующееся бинарное дерево поиска. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева «цвет». Если у узла нет потомков или родителя, то соответствующий указатель принимает значение NIL. Эти значения NIL мы будем рассматривать как указатели на внешние узлы (листья) дерева. Остальные узлы – внутренние.

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

Red-Black Trees Пример красно-черного дерева:

Red-Black Trees Если в красно-черном дереве N узлов, то можно доказать, что его высота не превосходит 2logN + 1, следовательно, максимальная высота растёт как O(logN). Операция поиска, а также операции вставки и удаления (это мы увидим чуть позднее) выполняются за O(h), где h – высота дерева, т.е. за O(logN).

Red-Black Trees Вставка : Вставляем узел в дерево, как если бы это было обычное бинарное дерево поиска, а затем окрашиваем его в красный цвет. Какие красно-черные свойства могут нарушиться при этом? 1) Каждый узел является красным или черным. 2) Корень дерева является черным. 3) Каждый лист дерева (NIL) является черным. 4) Если узел красный, то оба его дочерних узла черные. 5) Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов. Только свойства 2 и 4. Если нарушилось свойство 2, то значит вставляемый узел – единственный в дереве, и он является корнем. Тогда просто покрасим его в черный цвет.

Red-Black Trees Рассмотрим ситуацию, когда нарушается свойство 4 (Никакие два красных узла не могут непосредственно следовать друг за другом): Пусть вставляем узел z. Тогда родитель z – красный. Обозначим y – «дядя» z. Существует 3 случая (на самом деле их 6, но они симметричны): A B C DA B C DA B C D z y z z yy узел у красный.узел у черный и z правый узел у черный и z левый

Red-Black Trees 1 2 3

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

Red-Black Trees Удаление : Производится так же, как в обычном бинарном дереве: 1.Если у удаляемого узла Z нет детей, то просто удаляем его. 2.Если у Z ровно один ребенок, то удаляем Z, ребенка ставим на его место, добавляя соответствующие связи. Z

Red-Black Trees Удаление : 3. Если у Z два ребенка, то поступаем так: Ищем узел Y, значение которого больше (или меньше) чем значение Z, но так, чтобы между значениями Z и Y не было других значений в дереве. Другими словами, если отсортировать все элементы дерева, то узлы Z и Y будут стоять рядом. Z Y

Red-Black Trees Удаление : 3. (продолжение): Далее заменяем значение узла Z значением найденного Y. Так как копируется только значение, то нарушения красно- черных свойств нет. Проблемы возникают дальше, когда нам нужно извлечь узел Y из дерева. Далее, когда речь пойдет о удалении узла, мы будем иметь в виду именно узел Y. Потомка Y – обозначим X. Z Y X X

Red-Black Trees Удаление : Если удаляемый узел (Y) красного цвета, то все хорошо. (Нарушения красно-черных свойств не происходит) Если же он черного цвета, то могут возникнуть три проблемы: если удаляемый узел Y был корнем, а теперь корнем стал его красный потомок X, нарушается свойство 2. (Корень - черный) может возникнуть ситуация двух подряд идущих красных узлов (нарушение свойства 4) уменьшается черная высота для всего поддерева удаляемого узла (нарушение свойства 5)

Red-Black Trees Удаление : Попытаемся восстановить свойство 5: Будем считать, что при удалении Y как бы отдает свою «черноту» X, тогда X – «сверхчерный». Это значит, что при прохождении через X, мы будем добавлять дополнительную 1 к количеству черных узлов. Получается, что узел X окрашен либо "дважды черным", либо "красно-черным" цветом, что дает при подсчете черных узлов на пути, содержащем X, вклад, равный, соответственно, 2 или 1. (Нарушается 1 красно-черное свойство)

Red-Black Trees Цель: переместить дополнительную черноту вверх по дереву до тех пор, пока не выполнится одно из перечисленных условий: Удаление : 1)X указывает на красно-черный узел в этом случае мы просто делаем узел X "единожды черным". 2)X указывает на корень в этом случае мы просто убираем излишнюю черноту. 3)Можно выполнить некоторые повороты и перекраску, после которых двойная чернота будет устранена.

Red-Black Trees Удаление : Пусть W – «брат» X, т.е. второй потомок отца X. Будем рассматривать 4 возможных случая: Случай 1: узел w красный. Случай 2: узел w черный, оба его дочерних узла черные. Случай 3: узел w черный, его левый дочерний узел красный, а правый черный. Случай 4: узел w черный, его правый дочерний узел красный.

Red-Black Trees

Анализ : Оценим сложность алгоритма удаления: Поиск удаляемого узла Z - O(log n) Поиск «ближайшего к нему» Y - O(log n) Восстановление красно-черных свойств - O(log n): В случаях 1, 3 и 4 завершение работы происходит после выполнения постоянного числа изменений цвета и не более трех поворотов. В случае 2 указатель X перемещается вверх по дереву не более чем О (log n) раз, и никакие повороты при этом не выполняются. Общее время работы - O(log n).

Red-Black Trees Где используются? Контейнер map в реализации библиотеки STL языка C++; Класс TreeMap языка Java; Многие другие реализации ассоциативного массива в различных библиотеках в ядре Linux (для организации очередей запросов, в ext3)

AVL-trees АВЛ-дерево сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. Высота узла : - Высота листа равна 1. Высота нулевого указателя – 0. - Высота внутреннего узла есть максимум из высот его поддеревьев плюс 1. Для каждого узла хранится коэффициент симметрии (balance factor), имеющий три значения (-1, 0, 1) для обозначения, если высота левого поддерева правого соответственно. При всех остальных значениях узел (а значит и все дерево) считается несбалансированным.

AVL-trees Оценка высоты дерева: Обозначим N h – минимальное количество узлов в АВЛ-дереве высотой h Можно доказать, что дерево с высотой h должно содержать как минимум F h вершин, где F i i-ое число Фибоначчи. Так как F k+2 > k, то k log N 1.44log N = (1 + 5)/2 – золотое сечение Таким образом, h = O(log N). Операции поиска, а также вставки и удаления (про них мы еще поговорим) над деревом выполняются за O(log N).

AVL-trees Вставка: Заметим, что при вставке или удалении узла, высота некоторого поддерева может измениться максимум на 1. Следовательно, если свойство дерева нарушается, то это возможно только если коэффициент симметрии равен 2 (или -2). Чтобы восстановить свойство АВЛ-дерева воспользуемся поворотами.

AVL-trees Вставка: Вставим новый узел в качестве листа, как это делается в обычном бинарном дереве Будем рассматривать все вершины на пути от нового листа к корню дерева. Будем проверять, верно ли, что высоты левого и правого поддеревьев отличаются не больше чем на 1. Если да, то перейдем к предку рассматриваемого узла. Иначе, восстановим свойство, применяя либо одинарный, либо двойной поворот Известно, что для вставки требуется максимум один поворот, т.е. если сделали поворот, то дальше можно не подниматься по дереву.

AVL-trees Удаление: Удаляем узел как это делается в обычном бинарном дереве. Будем рассматривать все вершины на пути от удаляемого листа к корню дерева. Будем проверять, верно ли, что высоты левого и правого поддеревьев отличаются не больше чем на 1. Если да, то перейдем к предку рассматриваемого узла. Иначе, восстановим свойство, применяя либо одинарный, либо двойной поворот При удалении может потребоваться больше чем один поворот, следовательно продолжаем, пока не достигнем корня дерева.

AVL-trees M JR EU Q GTN X V L Удаляем L (требуется лево- правый поворот вокруг G) После восстановления J, узел M все еще остается несбалансированным Пример, когда при удалении может потребоваться не один поворот: M JR EU Q GTN X V L

AVL-trees Наглядная демонстрация работы АВЛ-дерева:

AVL-trees Эффективность Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно которой высота АВЛ-дерева с N внутренними вершинами заключена между log(N+1) и *log(N+2)-0.328, то есть высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших N имеет место оценка 1.04*log(N). Таким образом, выполнение базовых операций требует порядка log(N) сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.

AVL-trees АВЛ-деревья используются, когда нужен быстрый доступ к элементам дерева Могут использоваться для сортировки данных Где используются?

AVL vs Red-Black Сравнение красно-черных и АВЛ-деревьев: В худшем случае высота составляет: АВЛ-деревья * log(N+2) Красно-черные деревья - 2 * log(N+1) Следовательно, при поиске АВЛ-деревья работают быстрее красно-черных При вставке красно-черные деревья выполняют балансировку за O(1), АВЛ же за O(log N) Касательно удаления, здесь также выигрывают красно- черные, так как им потребуется O(1) (максимум 3 поворота), тогда как для АВЛ может потребоваться O(log N) И у тех, и у других все базовые операции над бинарными деревьями имеют сложность – O(log N)

AVL vs Red-Black Сравнение красно-черных и АВЛ-деревьев: Таким образом, АВЛ-деревья рекомендуется использовать, когда хочется быстрого поиска элемента в фиксированных данных Если же данные динамические, т.е. много операций вставки и удаления, то лучше использовать красно- черные деревья

Rank-Balanced Trees Вывод: Хочется совместить преимущества АВЛ и красно-черных деревьев: Маленькая высота Малое количество балансировок Простой алгоритм

Ranks Каждый узел имеет ранг – целое число, оценивающее высоту поддерева данного узла Будем считать, что листья имеют ранг 0, Отсутствующие узлы имеют ранг -1 Ранг-разность для ребенка - это разность между рангом родителя и рангом ребенка i-ребенок: узел с ранг-разностью i i,j-узел: дети этого узла имеют ранги i и j Рангом дерева будем называть ранг его корня

Ranked Binary Trees 1 f 1 1 e d b 2 a c Пример бинарного дерева с рангом: Синие цифры – ранг Черные – ранг-разность

Ranked Binary Trees АВЛ-деревья: каждый узел либо 1,1-, либо 1,2- Красно-черные: все ранг-разности либо 0, либо 1, никакой 0-ребенок не может быть отцом другого 0-ребенка RB-деревья: каждый узел 1,1-, 1,2-, или 2,2-узел (ранг-разность либо 1, либо 2) В каждом случае требуется дополнительный бит сбалансированности

Оценка высот n k = минимальное n для ранга k АВЛ-деревья: n 0 = 1, n 1 = 2, n k = n k-1 + n k n k = F k k log n 1.44log n RB-деревья: n 0 = 1, n 1 = 2, n k = 2n k-2, n k = 2 k/2 k 2log n Та же высота и для красно-черных деревьев F k = k- ое число Фибоначчи – золотое сечение F k+2 > k

43 b Вставим bВставим c 0 c 1 a Вставим a > > 1 0 Левый поворот вокруг b 0 1 Rank-Balanced Trees Уменьшим a Увеличим a Увеличим b Вставка:

44 > e d 2 Вставим e c b > Вставим d a 1 > Левый поворот вокруг d 12 Rank-Balanced Trees Вставим c Уменьшим c Увеличим c Увеличим b Увеличим d Вставка:

e d b a c 2 Rank-Balanced Trees Вставим e Вставим f > > > f Левый поворот вокруг d Уменьшим b Увеличим e Увеличим d Вставка:

46 1 Вставим f f 1 1 e d b 2 Rank-Balanced Trees a c Вставка:

Rank-Balanced Trees - без поворотов (нетерминирующий случай) - одинарный поворот - двойной поворот Все числа здесь – ранг-разности. Так как нет 2,2-узлов, то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов. Балансировка при вставке: - без поворотов (нетерминирующий случай) - одинарный поворот - двойной поворот Все числа здесь – ранг-разности. Так как нет 2,2-узлов, то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов.

Rank-Balanced Trees Если узел q встает на место удаляемой вершины, а p ее родитель, то нарушение происходит, если p – лист ранга 1 или если q – 3- ребенок. Удаление:

def e Удалим a Удалим f Удалим d 1 Поменяем с последующим Удалим 1 f 1 d b 2 Rank-Balanced Trees a c Двойной поворот вокруг c Дважды увеличим c Уменьшим b Дважды уменьшим e Удаление:

50 e c b Удалим f Rank-Balanced Trees Удаление:

Rank-Balanced Trees Балансировка при удалении: - поворотов нет (нетерминирующие случаи) - одинарный поворот - двойной поворот Выполнится не более двух поворотов!

Rank-Balanced Trees Существует теорема, что высота сбалансированного по рангу дерева не превосходит log m, где m – количество вставок в дерево. (d – количество удалений) Общая высота RB-дерева – min{2log n, log m} В сравнении с другими деревьями: Если m=n, то в точности как АВЛ-дерево, т.е. O(log m) ~ O(log N) Если d и m примерно равны, то высота приближается к O(2log N) – как красно-черное дерево

Rank-Balanced Trees Таким образом, RB-деревья выполняют меньше поворотов, чем красно-черные деревья, а также достигают лучшей оценки высоты дерева (приближается к высоте АВЛ-дерева) Совместили преимущества АВЛ и красно-черных деревьев

Ссылки Много примеров взято из работ Siddhartha Sen, Bernhard Haeupler, Robert E. Tarjan (Princeton University) tree_2001/ tree_2001/ И другие

С п а с и б о з а в н и м а н и е