- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Бинарное дерево
Содержание
- 2. Binary TreesОперации над элементами в деревьях: - поиск - вставка - удаление
- 3. Binary TreesОсновная проблема в бинарных деревьях поиска
- 4. Binary TreesРешение:Хранить в каждой вершине информацию о
- 5. ПоворотыОдинарные левый и правый повороты: сохраняют симметрический порядок; изменяют высоту; работают за O(1).
- 6. ПоворотыПример двойного правого поворота(двойной левый точно так же только симметрично)
- 7. Повороты
- 8. Balanced Search TreesRed-Black treesAVL treesWeight Balanced treesLLRB trees2,3 treesB treesBinaryMultiway
- 9. Red-Black TreesКрасно-черное дерево – самобалансирующееся бинарное дерево
- 10. Red-Black TreesКрасно-черное дерево обладает следующими свойствами:
- 11. Red-Black TreesПример красно-черного дерева:
- 12. Red-Black Trees Если в красно-черном
- 13. Red-Black TreesВставка:Вставляем узел в дерево, как если
- 14. Red-Black TreesРассмотрим ситуацию, когда нарушается свойство 4
- 15. Red-Black Trees123
- 16. Red-Black TreesАнализ:Оценим сложность алгоритма вставки:Поиск места для
- 17. Red-Black TreesУдаление:Производится так же, как в обычном
- 18. Red-Black TreesУдаление:3. Если у Z два ребенка,
- 19. Red-Black TreesУдаление:3. (продолжение): Далее заменяем
- 20. Red-Black TreesУдаление:Если удаляемый узел (Y) красного цвета,
- 21. Red-Black TreesУдаление: Попытаемся восстановить свойство 5:
- 22. Red-Black Trees Цель: переместить дополнительную черноту
- 23. Red-Black TreesУдаление:Пусть W – «брат» X, т.е.
- 24. Red-Black Trees
- 25. Red-Black TreesАнализ:Оценим сложность алгоритма удаления:Поиск удаляемого узла
- 26. Red-Black TreesГде используются? Контейнер map в реализации библиотеки STL языка C++;
- 27. AVL-trees АВЛ-дерево — сбалансированное по высоте двоичное дерево
- 28. AVL-treesОценка высоты дерева: Обозначим Nh –
- 29. AVL-treesВставка: Заметим, что при вставке
- 30. AVL-treesВставка: Вставим новый узел в качестве листа,
- 31. AVL-treesУдаление: Удаляем узел как это делается в
- 32. AVL-treesMJREUQGTNXVLУдаляем L(требуется лево-правый поворот вокруг G)После восстановления
- 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
- 34. AVL-treesЭффективность Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему,
- 35. AVL-trees АВЛ-деревья используются, когда нужен быстрый доступ
- 36. AVL vs Red-BlackСравнение красно-черных и АВЛ-деревьев:В худшем
- 37. AVL vs Red-BlackСравнение красно-черных и АВЛ-деревьев:
- 38. Rank-Balanced TreesВывод:Хочется совместить преимущества АВЛ и красно-черных деревьев: Маленькая высота Малое количество балансировок Простой алгоритм
- 39. Ranks Каждый узел имеет ранг –
- 40. Ranked Binary Trees1f11edb2ac1110001Пример бинарного дерева с рангом:Синие цифры – рангЧерные – ранг-разность
- 41. Ranked Binary TreesАВЛ-деревья: каждый узел либо 1,1-,
- 42. Оценка высотnk = минимальное n для ранга
- 43. bВставим bВставим c0c1aВставим a>>10Левый поворот вокруг b01Rank-Balanced TreesУменьшим a001Увеличим aУвеличим bВставка:
- 44. >ed2Вставим e001101cb>Вставим da1>Левый поворот вокруг d12Rank-Balanced TreesВставим cУменьшим c000011Увеличим cУвеличим bУвеличим dВставка:
- 45. 01e211dbac2Rank-Balanced TreesВставим eВставим f>>>f0210Левый поворот вокруг dУменьшим b1000012Увеличим eУвеличим dВставка:
- 46. 1Вставим ff11edb2Rank-Balanced Treesac1110001Вставка:
- 47. Rank-Balanced Trees без поворотов(нетерминирующий случай)- одинарный поворот-
- 48. Rank-Balanced Trees Если узел q встает
- 49. 210defeУдалим aУдалим fУдалим d1Поменяем с последующимУдалим1f1db2Rank-Balanced Treesac111000Двойной поворот вокруг cДважды увеличим cУменьшим bДважды уменьшим eУдаление:
- 50. ecbУдалим fRank-Balanced Trees20202Удаление:
- 51. Rank-Balanced TreesБалансировка при удалении:- поворотов нет(нетерминирующие случаи)- одинарный поворот- двойной поворотВыполнится не более двух поворотов!
- 52. Rank-Balanced Trees Существует теорема, что высота
- 53. Rank-Balanced Trees Таким образом, RB-деревья выполняют
- 54. Ссылки Много примеров взято из работ Siddhartha
- 55. Скачать презентацию
- 56. Похожие презентации
Binary TreesОперации над элементами в деревьях: - поиск - вставка - удаление
Слайд 3
Binary Trees
Основная проблема в бинарных деревьях поиска (BST)
– несбалансированность
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
Решение:
Хранить в каждой вершине информацию о сбалансированности
ее поддеревьев
После каждой вставки или удаления, если это необходимо,
изменять структуру дерева так, чтобы восстановить баланс. Далее пробегать по дереву и обновлять информацию о сбалансированностиВопрос: Как быстро и безопасно изменять структуру дерева?
Слайд 5
Повороты
Одинарные левый и правый повороты:
сохраняют симметрический порядок;
изменяют высоту;
работают за O(1).
Слайд 8
Balanced Search Trees
Red-Black trees
AVL trees
Weight Balanced trees
LLRB trees
2,3
trees
B trees
Binary
Multiway
Слайд 9
Red-Black Trees
Красно-черное дерево – самобалансирующееся бинарное дерево поиска.
Сбалансированность достигается за счет введения дополнительного атрибута узла дерева
— «цвет».Если у узла нет потомков или родителя, то соответствующий указатель принимает значение NIL. Эти значения NIL мы будем рассматривать как указатели на внешние узлы (листья) дерева. Остальные узлы – внутренние.
Слайд 10
Red-Black Trees
Красно-черное дерево обладает следующими свойствами:
1)
Каждый узел является красным или черным.
2) Корень
дерева является черным. 3) Каждый лист дерева (NIL) является черным.
4) Если узел — красный, то оба его дочерних узла — черные.
5) Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов.
Слайд 12
Red-Black Trees
Если в красно-черном дереве
N узлов, то можно доказать, что его высота не
превосходит 2logN + 1, следовательно, максимальная высота растёт как O(logN).Операция поиска, а также операции вставки и удаления (это мы увидим чуть позднее) выполняются за O(h), где h – высота дерева, т.е. за O(logN).
Слайд 13
Red-Black Trees
Вставка:
Вставляем узел в дерево, как если бы
это было обычное бинарное дерево поиска, а затем окрашиваем
его в красный цвет.Какие красно-черные свойства могут нарушиться при этом?
1) Каждый узел является красным или черным.
2) Корень дерева является черным.
3) Каждый лист дерева (NIL) является черным.
4) Если узел — красный, то оба его дочерних узла — черные.
5) Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов.
Только свойства 2 и 4. Если нарушилось свойство 2, то значит вставляемый узел – единственный в дереве, и он является корнем. Тогда просто покрасим его в черный цвет.
Слайд 14
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 — левый
Слайд 16
Red-Black Trees
Анализ:
Оценим сложность алгоритма вставки:
Поиск места для вставки
нового узла - O(log n)
Восстановление красно-черных свойств - O(log
n):В случаях 2 и 3 завершение работы происходит после выполнения постоянного числа изменений цвета и не более двух поворотов. В случае 1 указатель z перемещается вверх по дереву сразу на два уровня (т.е. не более чем O(log n) операций), и никакие повороты при этом не выполняются.
Общее время работы - O(log n).
Слайд 17
Red-Black Trees
Удаление:
Производится так же, как в обычном бинарном
дереве:
Если у удаляемого узла Z нет детей, то просто
удаляем его.Если у Z ровно один ребенок, то удаляем Z, ребенка ставим на его место, добавляя соответствующие связи.
Z
Слайд 18
Red-Black Trees
Удаление:
3. Если у Z два ребенка, то
поступаем так:
Ищем узел Y, значение которого
больше (или меньше) чем значение Z, но так, чтобы между значениями Z и Y не было других значений в дереве. Другими словами, если отсортировать все элементы дерева, то узлы Z и Y будут стоять рядом.Z
Y
Слайд 19
Red-Black Trees
Удаление:
3. (продолжение):
Далее заменяем значение
узла Z значением найденного Y. Так как копируется только
значение, то нарушения красно-черных свойств нет. Проблемы возникают дальше, когда нам нужно извлечь узел Y из дерева. Далее, когда речь пойдет о удалении узла, мы будем иметь в виду именно узел Y. Потомка Y – обозначим X.Z
Y
X
X
Слайд 20
Red-Black Trees
Удаление:
Если удаляемый узел (Y) красного цвета, то
все хорошо. (Нарушения красно-черных свойств не происходит)
Если же он
черного цвета, то могут возникнуть три проблемы: если удаляемый узел Y был корнем, а теперь корнем стал его красный потомок X, нарушается свойство 2. (Корень - черный)
может возникнуть ситуация двух подряд идущих красных узлов (нарушение свойства 4)
уменьшается черная высота для всего поддерева удаляемого узла (нарушение свойства 5)
Слайд 21
Red-Black Trees
Удаление:
Попытаемся восстановить свойство 5:
Будем считать, что при удалении Y как бы отдает
свою «черноту» X, тогда X – «сверхчерный». Это значит, что при прохождении через X, мы будем добавлять дополнительную 1 к количеству черных узлов.Получается, что узел X окрашен либо "дважды черным", либо "красно-черным" цветом, что дает при подсчете черных узлов на пути, содержащем X, вклад, равный, соответственно, 2 или 1.
(Нарушается 1 красно-черное свойство)
Слайд 22
Red-Black Trees
Цель: переместить дополнительную черноту вверх
по дереву до тех пор, пока не выполнится одно
из перечисленных условий:Удаление:
X указывает на красно-черный узел — в этом случае мы просто делаем узел X "единожды черным".
X указывает на корень — в этом случае мы просто убираем излишнюю черноту.
Можно выполнить некоторые повороты и перекраску, после которых двойная чернота будет устранена.
Слайд 23
Red-Black Trees
Удаление:
Пусть W – «брат» X, т.е. второй
потомок отца X.
Будем рассматривать 4 возможных случая:
Случай 1: узел
w красный.Случай 2: узел w черный, оба его дочерних узла черные.
Случай 3: узел w черный, его левый дочерний узел красный, а правый — черный.
Случай 4: узел w черный, его правый дочерний узел красный.
Слайд 25
Red-Black Trees
Анализ:
Оценим сложность алгоритма удаления:
Поиск удаляемого узла Z
- 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++;
Класс
TreeMap языка Java;
Многие другие реализации ассоциативного массива в различных библиотеках
в
ядре Linux (для организации очередей запросов, в ext3)
Слайд 27
AVL-trees
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска:
для каждой его вершины высота её двух поддеревьев различается
не более чем на 1.Высота узла :
Высота листа равна 1. Высота нулевого указателя – 0.
Высота внутреннего узла есть максимум из высот его поддеревьев плюс 1.
Для каждого узла хранится коэффициент симметрии (balance factor), имеющий три значения (-1, 0, 1) для обозначения, если высота левого поддерева <, = или > правого соответственно. При всех остальных значениях узел (а значит и все дерево) считается несбалансированным.
Слайд 28
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
Вставка:
Заметим, что при вставке или
удалении узла, высота некоторого поддерева может измениться максимум на
1. Следовательно, если свойство дерева нарушается, то это возможно только если коэффициент симметрии равен 2 (или -2).Чтобы восстановить свойство АВЛ-дерева воспользуемся поворотами.
Слайд 30
AVL-trees
Вставка:
Вставим новый узел в качестве листа, как
это делается в обычном бинарном дереве
Будем рассматривать все
вершины на пути от нового листа к корню дерева. Будем проверять, верно ли, что высоты левого и правого поддеревьев отличаются не больше чем на 1.Если да, то перейдем к предку рассматриваемого узла. Иначе, восстановим свойство, применяя либо одинарный, либо двойной поворот
Известно, что для вставки требуется максимум один поворот, т.е. если сделали поворот, то дальше можно не подниматься по дереву.
Слайд 31
AVL-trees
Удаление:
Удаляем узел как это делается в обычном
бинарном дереве.
Будем рассматривать все вершины на пути от
удаляемого листа к корню дерева. Будем проверять, верно ли, что высоты левого и правого поддеревьев отличаются не больше чем на 1.Если да, то перейдем к предку рассматриваемого узла. Иначе, восстановим свойство, применяя либо одинарный, либо двойной поворот
При удалении может потребоваться больше чем один поворот, следовательно продолжаем, пока не достигнем корня дерева.
Слайд 32
AVL-trees
M
J
R
E
U
Q
G
T
N
X
V
L
Удаляем L
(требуется лево-правый поворот вокруг G)
После восстановления J,
узел 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
Слайд 34
AVL-trees
Эффективность
Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно
которой высота АВЛ-дерева с N внутренними вершинами заключена между
log(N+1) и 1.4404*log(N+2)-0.328, то есть высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших N имеет место оценка 1.04*log(N). Таким образом, выполнение базовых операций требует порядка log(N) сравнений.Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.
Слайд 35
AVL-trees
АВЛ-деревья используются, когда нужен быстрый доступ к
элементам дерева
Могут использоваться для сортировки данных
Где используются?
Слайд 36
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
Сравнение красно-черных и АВЛ-деревьев:
Таким
образом,
АВЛ-деревья рекомендуется использовать, когда хочется быстрого поиска элемента в
фиксированных данныхЕсли же данные динамические, т.е. много операций вставки и удаления, то лучше использовать красно-черные деревья
Слайд 38
Rank-Balanced Trees
Вывод:
Хочется совместить преимущества АВЛ и красно-черных деревьев:
Маленькая высота
Малое количество балансировок
Простой алгоритм
Слайд 39
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
Пример бинарного дерева с рангом:
Синие цифры
– ранг
Черные – ранг-разность
Слайд 41
Ranked Binary Trees
АВЛ-деревья: каждый узел либо 1,1-, либо
1,2-
Красно-черные: все ранг-разности либо 0, либо 1, никакой 0-ребенок
не может быть отцом другого 0-ребенкаRB-деревья: каждый узел 1,1-, 1,2-, или 2,2-узел (ранг-разность либо 1, либо 2)
В каждом случае требуется дополнительный бит сбалансированности
Слайд 42
Оценка высот
nk = минимальное n для ранга k
АВЛ-деревья:
n0
= 1, n1 = 2, nk = nk-1 +
nk-2 + 1nk = 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
Уменьшим
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
Уменьшим
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
Увеличим
e
Увеличим d
Вставка:
Слайд 47
Rank-Balanced Trees
без поворотов
(нетерминирующий случай)
- одинарный поворот
- двойной
поворот
Все числа здесь – ранг-разности. Так как нет 2,2-узлов,
то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов.Балансировка при вставке:
без поворотов
(нетерминирующий случай)
- одинарный поворот
- двойной поворот
Все числа здесь – ранг-разности. Так как нет 2,2-узлов, то ведет себя в точности как АВЛ-дерево. Выполнится не более двух поворотов.
Слайд 48
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
Двойной поворот
вокруг c
Дважды увеличим c
Уменьшим b
Дважды уменьшим e
Удаление:
Слайд 51
Rank-Balanced Trees
Балансировка при удалении:
- поворотов нет
(нетерминирующие случаи)
- одинарный
поворот
- двойной поворот
Выполнится не более двух поворотов!
Слайд 52
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-деревья выполняют меньше
поворотов, чем красно-черные деревья, а также достигают лучшей оценки
высоты дерева (приближается к высоте АВЛ-дерева) Совместили преимущества АВЛ и красно-черных деревьев
Слайд 54
Ссылки
Много примеров взято из работ Siddhartha Sen,
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/ И другие
