Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Бинарное дерево

Содержание

Binary TreesОперации над элементами в деревьях: - поиск - вставка - удаление
Rank-Balanced TreesЛокис ВасилийКН-301Екатеринбург, 2010 Binary TreesОперации над элементами в деревьях:	- поиск	- вставка	- удаление Binary TreesОсновная проблема в бинарных деревьях поиска (BST) – несбалансированностьabcdefПоиск ~ O(n)Вставка Binary TreesРешение:Хранить в каждой вершине информацию о сбалансированности ее поддеревьевПосле каждой вставки ПоворотыОдинарные левый и правый повороты: сохраняют симметрический порядок; изменяют высоту; работают за O(1). ПоворотыПример двойного правого поворота(двойной левый точно так же только симметрично) Повороты Balanced Search TreesRed-Black treesAVL treesWeight Balanced treesLLRB trees2,3 treesB treesBinaryMultiway Red-Black TreesКрасно-черное дерево – самобалансирующееся бинарное дерево поиска. Сбалансированность достигается за счет Red-Black TreesКрасно-черное дерево обладает следующими свойствами:  1) Каждый узел является красным Red-Black TreesПример красно-черного дерева: Red-Black Trees   Если в красно-черном дереве N узлов, то можно Red-Black TreesВставка:Вставляем узел в дерево, как если бы это было обычное бинарное Red-Black TreesРассмотрим ситуацию, когда нарушается свойство 4 (Никакие два красных узла не Red-Black Trees123 Red-Black TreesАнализ:Оценим сложность алгоритма вставки:Поиск места для вставки нового узла - O(log Red-Black TreesУдаление:Производится так же, как в обычном бинарном дереве:Если у удаляемого узла Red-Black TreesУдаление:3. Если у Z два ребенка, то поступаем так: Red-Black TreesУдаление:3. (продолжение):   Далее заменяем значение узла Z значением найденного Red-Black TreesУдаление:Если удаляемый узел (Y) красного цвета, то все хорошо. (Нарушения красно-черных Red-Black TreesУдаление:  Попытаемся восстановить свойство 5:  Будем считать, что при Red-Black Trees  Цель: переместить дополнительную черноту вверх по дереву до тех Red-Black TreesУдаление:Пусть W – «брат» X, т.е. второй потомок отца X.Будем рассматривать Red-Black Trees Red-Black TreesАнализ:Оценим сложность алгоритма удаления:Поиск удаляемого узла Z - O(log n)Поиск «ближайшего Red-Black TreesГде используются? Контейнер map в реализации библиотеки STL языка C++; Класс TreeMap языка Java; Многие другие AVL-trees  АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины AVL-treesОценка высоты дерева:  Обозначим Nh – минимальное количество узлов в АВЛ-дереве AVL-treesВставка:   Заметим, что при вставке или удалении узла, высота некоторого AVL-treesВставка: Вставим новый узел в качестве листа, как это делается в обычном AVL-treesУдаление: Удаляем узел как это делается в обычном бинарном дереве. Будем рассматривать AVL-treesMJREUQGTNXVLУдаляем L(требуется лево-правый поворот вокруг G)После восстановления J, узел M все еще AVL-treesНаглядная демонстрация работы АВЛ-дерева:http://www.strille.net/works/media_technology_projects/avl-tree_2001/http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html AVL-treesЭффективность  Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно которой высота АВЛ-дерева с AVL-trees АВЛ-деревья используются, когда нужен быстрый доступ к элементам дерева Могут использоваться AVL vs Red-BlackСравнение красно-черных и АВЛ-деревьев:В худшем случае высота составляет: 	АВЛ-деревья - AVL vs Red-BlackСравнение красно-черных и АВЛ-деревьев:  Таким образом,АВЛ-деревья рекомендуется использовать, когда Rank-Balanced TreesВывод:Хочется совместить преимущества АВЛ и красно-черных деревьев: Маленькая высота Малое количество балансировок Простой алгоритм Ranks  Каждый узел имеет ранг – целое число, оценивающее высоту поддерева Ranked Binary Trees1f11edb2ac1110001Пример бинарного дерева с рангом:Синие цифры – рангЧерные – ранг-разность Ranked Binary TreesАВЛ-деревья: каждый узел либо 1,1-, либо 1,2-Красно-черные: все ранг-разности либо Оценка высотnk = минимальное n для ранга kАВЛ-деревья:	n0 = 1, n1 = bВставим bВставим c0c1aВставим a>>10Левый поворот вокруг b01Rank-Balanced TreesУменьшим a001Увеличим aУвеличим bВставка: >ed2Вставим e001101cb>Вставим da1>Левый поворот вокруг d12Rank-Balanced TreesВставим cУменьшим c000011Увеличим cУвеличим bУвеличим dВставка: 01e211dbac2Rank-Balanced TreesВставим eВставим f>>>f0210Левый поворот вокруг dУменьшим b1000012Увеличим eУвеличим dВставка: 1Вставим ff11edb2Rank-Balanced Treesac1110001Вставка: Rank-Balanced Trees без поворотов(нетерминирующий случай)- одинарный поворот- двойной поворотВсе числа здесь – Rank-Balanced Trees  Если узел q встает на место удаляемой вершины, а 210defeУдалим aУдалим fУдалим d1Поменяем с последующимУдалим1f1db2Rank-Balanced Treesac111000Двойной поворот вокруг cДважды увеличим cУменьшим bДважды уменьшим eУдаление: ecbУдалим fRank-Balanced Trees20202Удаление: Rank-Balanced TreesБалансировка при удалении:- поворотов нет(нетерминирующие случаи)- одинарный поворот- двойной поворотВыполнится не более двух поворотов! Rank-Balanced Trees  Существует теорема, что высота сбалансированного по рангу дерева не Rank-Balanced Trees  Таким образом, RB-деревья выполняют меньше поворотов, чем красно-черные деревья, Ссылки Много примеров взято из работ Siddhartha Sen, Bernhard Haeupler, Robert E. С п а с и б оз а  в н и
Слайды презентации

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

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

удаление


Слайд 3 Binary Trees
Основная проблема в бинарных деревьях поиска (BST)

Binary TreesОсновная проблема в бинарных деревьях поиска (BST) – несбалансированностьabcdefПоиск ~

– несбалансированность
a
b
c
d
e
f
Поиск ~ O(n)
Вставка ~ O(n)
Удаление ~ O(n)

Хочется,

чтобы дерево было всегда идеально сбалансированным

c

b

d

e

f

a

Поиск ~ O(log n)
Вставка ~ O(log n)
Удаление ~ O(log n)


Слайд 4 Binary Trees
Решение:
Хранить в каждой вершине информацию о сбалансированности

Binary TreesРешение:Хранить в каждой вершине информацию о сбалансированности ее поддеревьевПосле каждой

ее поддеревьев
После каждой вставки или удаления, если это необходимо,

изменять структуру дерева так, чтобы восстановить баланс. Далее пробегать по дереву и обновлять информацию о сбалансированности

Вопрос: Как быстро и безопасно изменять структуру дерева?


Слайд 5 Повороты
Одинарные левый и правый повороты:
сохраняют симметрический порядок;

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

изменяют высоту;
работают за O(1).


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

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

только симметрично)


Слайд 7 Повороты

Повороты

Слайд 8 Balanced Search Trees


Red-Black trees
AVL trees
Weight Balanced trees
LLRB trees
2,3

Balanced Search TreesRed-Black treesAVL treesWeight Balanced treesLLRB trees2,3 treesB treesBinaryMultiway

trees
B trees
Binary
Multiway


Слайд 9 Red-Black Trees
Красно-черное дерево – самобалансирующееся бинарное дерево поиска.

Red-Black TreesКрасно-черное дерево – самобалансирующееся бинарное дерево поиска. Сбалансированность достигается за

Сбалансированность достигается за счет введения дополнительного атрибута узла дерева

— «цвет».

Если у узла нет потомков или родителя, то соответствующий указатель принимает значение NIL. Эти значения NIL мы будем рассматривать как указатели на внешние узлы (листья) дерева. Остальные узлы – внутренние.


Слайд 10 Red-Black Trees
Красно-черное дерево обладает следующими свойствами:

1)

Red-Black TreesКрасно-черное дерево обладает следующими свойствами: 1) Каждый узел является красным

Каждый узел является красным или черным.

2) Корень

дерева является черным.

3) Каждый лист дерева (NIL) является черным.

4) Если узел — красный, то оба его дочерних узла — черные.

5) Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов.


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

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

Слайд 12 Red-Black Trees
Если в красно-черном дереве

Red-Black Trees  Если в красно-черном дереве N узлов, то можно

N узлов, то можно доказать, что его высота не

превосходит 2logN + 1, следовательно, максимальная высота растёт как O(logN).


Операция поиска, а также операции вставки и удаления (это мы увидим чуть позднее) выполняются за O(h), где h – высота дерева, т.е. за O(logN).

Слайд 13 Red-Black Trees
Вставка:
Вставляем узел в дерево, как если бы

Red-Black TreesВставка:Вставляем узел в дерево, как если бы это было обычное

это было обычное бинарное дерево поиска, а затем окрашиваем

его в красный цвет.

Какие красно-черные свойства могут нарушиться при этом?

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

Только свойства 2 и 4. Если нарушилось свойство 2, то значит вставляемый узел – единственный в дереве, и он является корнем. Тогда просто покрасим его в черный цвет.


Слайд 14 Red-Black Trees
Рассмотрим ситуацию, когда нарушается свойство 4 (Никакие

Red-Black TreesРассмотрим ситуацию, когда нарушается свойство 4 (Никакие два красных узла

два красных узла не могут непосредственно следовать друг за

другом):
Пусть вставляем узел z. Тогда родитель z – красный. Обозначим y – «дядя» z.
Существует 3 случая (на самом деле их 6, но они симметричны):

A

B

C

D

A

B

C

D

A

B

C

D

z

y

z

z

y

y

узел у красный.

узел у черный и z — правый

узел у черный и z — левый


Слайд 15 Red-Black Trees




1
2
3

Red-Black Trees123

Слайд 16 Red-Black Trees
Анализ:
Оценим сложность алгоритма вставки:
Поиск места для вставки

Red-Black TreesАнализ:Оценим сложность алгоритма вставки:Поиск места для вставки нового узла -

нового узла - O(log n)
Восстановление красно-черных свойств - O(log

n):

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

Общее время работы - O(log n).


Слайд 17 Red-Black Trees
Удаление:
Производится так же, как в обычном бинарном

Red-Black TreesУдаление:Производится так же, как в обычном бинарном дереве:Если у удаляемого

дереве:
Если у удаляемого узла Z нет детей, то просто

удаляем его.
Если у Z ровно один ребенок, то удаляем Z, ребенка ставим на его место, добавляя соответствующие связи.

Z


Слайд 18 Red-Black Trees
Удаление:
3. Если у Z два ребенка, то

Red-Black TreesУдаление:3. Если у Z два ребенка, то поступаем так:

поступаем так:
Ищем узел Y, значение которого

больше (или меньше) чем значение Z, но так, чтобы между значениями Z и Y не было других значений в дереве. Другими словами, если отсортировать все элементы дерева, то узлы Z и Y будут стоять рядом.

Z

Y


Слайд 19 Red-Black Trees
Удаление:
3. (продолжение):

Далее заменяем значение

Red-Black TreesУдаление:3. (продолжение):  Далее заменяем значение узла Z значением найденного

узла Z значением найденного Y. Так как копируется только

значение, то нарушения красно-черных свойств нет. Проблемы возникают дальше, когда нам нужно извлечь узел Y из дерева. Далее, когда речь пойдет о удалении узла, мы будем иметь в виду именно узел Y. Потомка Y – обозначим X.

Z

Y

X

X


Слайд 20 Red-Black Trees
Удаление:
Если удаляемый узел (Y) красного цвета, то

Red-Black TreesУдаление:Если удаляемый узел (Y) красного цвета, то все хорошо. (Нарушения

все хорошо. (Нарушения красно-черных свойств не происходит)
Если же он

черного цвета, то могут возникнуть три проблемы:

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


Слайд 21 Red-Black Trees
Удаление:
Попытаемся восстановить свойство 5:

Red-Black TreesУдаление: Попытаемся восстановить свойство 5: Будем считать, что при удалении

Будем считать, что при удалении Y как бы отдает

свою «черноту» X, тогда X – «сверхчерный». Это значит, что при прохождении через X, мы будем добавлять дополнительную 1 к количеству черных узлов.

Получается, что узел X окрашен либо "дважды черным", либо "красно-черным" цветом, что дает при подсчете черных узлов на пути, содержащем X, вклад, равный, соответственно, 2 или 1.
(Нарушается 1 красно-черное свойство)

Слайд 22 Red-Black Trees
Цель: переместить дополнительную черноту вверх

Red-Black Trees Цель: переместить дополнительную черноту вверх по дереву до тех

по дереву до тех пор, пока не выполнится одно

из перечисленных условий:

Удаление:

X указывает на красно-черный узел — в этом случае мы просто делаем узел X "единожды черным".

X указывает на корень — в этом случае мы просто убираем излишнюю черноту.

Можно выполнить некоторые повороты и перекраску, после которых двойная чернота будет устранена.


Слайд 23 Red-Black Trees
Удаление:
Пусть W – «брат» X, т.е. второй

Red-Black TreesУдаление:Пусть W – «брат» X, т.е. второй потомок отца X.Будем

потомок отца X.
Будем рассматривать 4 возможных случая:

Случай 1: узел

w красный.

Случай 2: узел w черный, оба его дочерних узла черные.

Случай 3: узел w черный, его левый дочерний узел красный, а правый — черный.

Случай 4: узел w черный, его правый дочерний узел красный.

Слайд 24 Red-Black Trees

Red-Black Trees

Слайд 25 Red-Black Trees
Анализ:
Оценим сложность алгоритма удаления:

Поиск удаляемого узла Z

Red-Black TreesАнализ:Оценим сложность алгоритма удаления:Поиск удаляемого узла Z - O(log n)Поиск

- O(log n)
Поиск «ближайшего к нему» Y - O(log

n)

Восстановление красно-черных свойств - O(log n):

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

Общее время работы - O(log n).


Слайд 26 Red-Black Trees
Где используются?
Контейнер map в реализации библиотеки STL языка C++;
Класс

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

TreeMap языка Java;
Многие другие реализации ассоциативного массива в различных библиотеках
в

ядре Linux (для организации очередей запросов, в ext3)

Слайд 27 AVL-trees
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска:

AVL-trees АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины

для каждой его вершины высота её двух поддеревьев различается

не более чем на 1.

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


Слайд 28 AVL-trees
Оценка высоты дерева:
Обозначим Nh – минимальное

AVL-treesОценка высоты дерева: Обозначим Nh – минимальное количество узлов в АВЛ-дереве

количество узлов в АВЛ-дереве высотой h
Можно доказать,

что дерево с высотой h должно содержать как минимум Fh вершин, где Fi — i-ое число Фибоначчи. Так как Fk+2 > φk, то k ≤ logφ N ≈ 1.44log N

φ = (1 + √5)/2 – золотое сечение

Таким образом, h = O(log N).

Операции поиска, а также вставки и удаления (про них мы еще поговорим) над деревом выполняются за O(log N).


Слайд 29 AVL-trees
Вставка:
Заметим, что при вставке или

AVL-treesВставка:  Заметим, что при вставке или удалении узла, высота некоторого

удалении узла, высота некоторого поддерева может измениться максимум на

1. Следовательно, если свойство дерева нарушается, то это возможно только если коэффициент симметрии равен 2 (или -2).

Чтобы восстановить свойство АВЛ-дерева воспользуемся поворотами.

Слайд 30 AVL-trees
Вставка:
Вставим новый узел в качестве листа, как

AVL-treesВставка: Вставим новый узел в качестве листа, как это делается в

это делается в обычном бинарном дереве
Будем рассматривать все

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

Слайд 31 AVL-trees
Удаление:
Удаляем узел как это делается в обычном

AVL-treesУдаление: Удаляем узел как это делается в обычном бинарном дереве. Будем

бинарном дереве.
Будем рассматривать все вершины на пути от

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

Слайд 32 AVL-trees

M


J
R

E

U

Q

G

T

N

X

V

L

Удаляем L
(требуется лево-правый поворот вокруг G)
После восстановления J,

AVL-treesMJREUQGTNXVLУдаляем L(требуется лево-правый поворот вокруг G)После восстановления J, узел M все

узел M все еще остается несбалансированным
Пример, когда при удалении

может потребоваться не один поворот:


M



J

R


E


U


Q


G


T


N


X


V


L


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

http://www.strille.net/works/media_technology_projects/avl-tree_2001/
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

AVL-treesНаглядная демонстрация работы АВЛ-дерева:http://www.strille.net/works/media_technology_projects/avl-tree_2001/http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

Слайд 34 AVL-trees
Эффективность
Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно

AVL-treesЭффективность Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно которой высота АВЛ-дерева с

которой высота АВЛ-дерева с N внутренними вершинами заключена между

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

Слайд 35 AVL-trees
АВЛ-деревья используются, когда нужен быстрый доступ к

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

элементам дерева
Могут использоваться для сортировки данных
Где используются?


Слайд 36 AVL vs Red-Black

Сравнение красно-черных и АВЛ-деревьев:
В худшем случае

AVL vs Red-BlackСравнение красно-черных и АВЛ-деревьев:В худшем случае высота составляет: 	АВЛ-деревья

высота составляет:
АВЛ-деревья - 1.44 * log(N+2) - 0.33
Красно-черные

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

И у тех, и у других все базовые операции над бинарными деревьями имеют сложность – O(log N)


Слайд 37 AVL vs Red-Black
Сравнение красно-черных и АВЛ-деревьев:
Таким

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

образом,
АВЛ-деревья рекомендуется использовать, когда хочется быстрого поиска элемента в

фиксированных данных
Если же данные динамические, т.е. много операций вставки и удаления, то лучше использовать красно-черные деревья

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

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

Маленькая высота
Малое количество балансировок
Простой алгоритм


Слайд 39 Ranks
Каждый узел имеет ранг – целое

Ranks Каждый узел имеет ранг – целое число, оценивающее высоту поддерева

число, оценивающее высоту поддерева данного узла
Будем считать, что листья

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

Рангом дерева будем называть ранг его корня


Слайд 40 Ranked Binary Trees
1
f
1
1
e
d
b
2
a
c
1
1
1
0
0
0
1
Пример бинарного дерева с рангом:
Синие цифры

Ranked Binary Trees1f11edb2ac1110001Пример бинарного дерева с рангом:Синие цифры – рангЧерные – ранг-разность

– ранг
Черные – ранг-разность


Слайд 41 Ranked Binary Trees
АВЛ-деревья: каждый узел либо 1,1-, либо

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

1,2-

Красно-черные: все ранг-разности либо 0, либо 1, никакой 0-ребенок

не может быть отцом другого 0-ребенка

RB-деревья: каждый узел 1,1-, 1,2-, или 2,2-узел (ранг-разность либо 1, либо 2)

В каждом случае требуется дополнительный бит сбалансированности


Слайд 42 Оценка высот
nk = минимальное n для ранга k

АВЛ-деревья:
n0

Оценка высотnk = минимальное n для ранга kАВЛ-деревья:	n0 = 1, n1

= 1, n1 = 2, nk = nk-1 +

nk-2 + 1
nk = Fk+3 - 1 ⇒ k ≤ logφ n ≈ 1.44log n

RB-деревья:
n0 = 1, n1 = 2, nk = 2nk-2,
nk = 2 ⎡k/2⎤ ⇒ k ≤ 2log n

Та же высота и для красно-черных деревьев

Fk = k-ое число Фибоначчи
φ – золотое сечение

Fk+2 > φk


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

bВставим bВставим c0c1aВставим a>>10Левый поворот вокруг b01Rank-Balanced TreesУменьшим a001Увеличим aУвеличим bВставка:

a
0
0
1
Увеличим a
Увеличим b
Вставка:


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

>ed2Вставим e001101cb>Вставим da1>Левый поворот вокруг d12Rank-Balanced TreesВставим cУменьшим c000011Увеличим cУвеличим bУвеличим dВставка:

c
0
0
0
0
1
1
Увеличим c
Увеличим b
Увеличим d
Вставка:


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

01e211dbac2Rank-Balanced TreesВставим eВставим f>>>f0210Левый поворот вокруг dУменьшим b1000012Увеличим eУвеличим dВставка:

e
Увеличим d
Вставка:


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

1Вставим ff11edb2Rank-Balanced Treesac1110001Вставка:

Слайд 47 Rank-Balanced Trees
без поворотов
(нетерминирующий случай)
- одинарный поворот
- двойной

Rank-Balanced Trees без поворотов(нетерминирующий случай)- одинарный поворот- двойной поворотВсе числа здесь

поворот
Все числа здесь – ранг-разности. Так как нет 2,2-узлов,

то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов.

Балансировка при вставке:

без поворотов
(нетерминирующий случай)

- одинарный поворот

- двойной поворот

Все числа здесь – ранг-разности. Так как нет 2,2-узлов, то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов.


Слайд 48 Rank-Balanced Trees
Если узел q встает на

Rank-Balanced Trees Если узел q встает на место удаляемой вершины, а

место удаляемой вершины, а p ее родитель, то нарушение

происходит, если p – лист ранга 1 или если q – 3-ребенок.

Удаление:


Слайд 49 2
1
0
d
e
f
e
Удалим a
Удалим f
Удалим d
1
Поменяем с последующим
Удалим
1
f
1
d
b
2
Rank-Balanced Trees
a
c
1
1
1
0
0
0
Двойной поворот

210defeУдалим aУдалим fУдалим d1Поменяем с последующимУдалим1f1db2Rank-Balanced Treesac111000Двойной поворот вокруг cДважды увеличим cУменьшим bДважды уменьшим eУдаление:

вокруг c
Дважды увеличим c
Уменьшим b
Дважды уменьшим e
Удаление:


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

ecbУдалим fRank-Balanced Trees20202Удаление:

Слайд 51 Rank-Balanced Trees
Балансировка при удалении:

- поворотов нет
(нетерминирующие случаи)
- одинарный

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

поворот
- двойной поворот
Выполнится не более двух поворотов!


Слайд 52 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) – как красно-черное дерево


Слайд 53 Rank-Balanced Trees
Таким образом, RB-деревья выполняют меньше

Rank-Balanced Trees Таким образом, RB-деревья выполняют меньше поворотов, чем красно-черные деревья,

поворотов, чем красно-черные деревья, а также достигают лучшей оценки

высоты дерева (приближается к высоте АВЛ-дерева)


Совместили преимущества АВЛ и красно-черных деревьев


Слайд 54 Ссылки
Много примеров взято из работ Siddhartha Sen,

Ссылки Много примеров взято из работ Siddhartha Sen, Bernhard Haeupler, Robert

Bernhard Haeupler, Robert E. Tarjan (Princeton University)
http://en.wikipedia.org/wiki/AVL_tree
http://en.wikipedia.org/wiki/Red-black_tree

http://www.strille.net/works/media_technology_projects/avl-tree_2001/
И другие

  • Имя файла: binarnoe-derevo.pptx
  • Количество просмотров: 164
  • Количество скачиваний: 0