Компьютер
<<  Поиск информации в компьютере Тест по компьютеру  >>
Rank-Balanced Trees
Rank-Balanced Trees
Операции над элементами в деревьях
Операции над элементами в деревьях
Проблема в бинарных деревьях
Проблема в бинарных деревьях
Баланс
Баланс
Повороты
Повороты
Пример двойного правого поворота
Пример двойного правого поворота
Повороты
Повороты
Balanced Search Trees
Balanced Search Trees
Самобалансирующееся бинарное дерево поиска
Самобалансирующееся бинарное дерево поиска
Красно-черное дерево
Красно-черное дерево
Пример красно-черного дерева
Пример красно-черного дерева
Высота
Высота
Вставка
Вставка
Свойство
Свойство
1
1
Анализ
Анализ
Удаление
Удаление
Узел
Узел
Значение узла
Значение узла
Удаляемый узел
Удаляемый узел
Красно-черное свойство
Красно-черное свойство
Красно-черный узел
Красно-черный узел
Левый дочерний узел
Левый дочерний узел
Red-Black Trees
Red-Black Trees
Сложность алгоритма удаления
Сложность алгоритма удаления
Контейнер
Контейнер
Сбалансированное по высоте двоичное дерево
Сбалансированное по высоте двоичное дерево
Оценка высоты дерева
Оценка высоты дерева
Высота некоторого поддерева
Высота некоторого поддерева
Новый узел
Новый узел
Вершины
Вершины
Поворот
Поворот
Наглядная демонстрация
Наглядная демонстрация
Эффективность
Эффективность
АВЛ-деревья
АВЛ-деревья
AVL vs Red-Black
AVL vs Red-Black
АВЛ-деревьев
АВЛ-деревьев
Преимущества
Преимущества
Ranks
Ranks
Ranked Binary Trees
Ranked Binary Trees
Ранг-разности
Ранг-разности
Оценка высот
Оценка высот
Вставим a
Вставим a
Вставим d
Вставим d
Вставим f
Вставим f
Вставим
Вставим
Балансировка при вставке
Балансировка при вставке
Узел q
Узел q
Удалим d
Удалим d
Удалим f
Удалим f
Балансировка при удалении
Балансировка при удалении
Теорема
Теорема
RB-деревья
RB-деревья
Ссылки
Ссылки
З а в н и м а н и е
З а в н и м а н и е
Презентация «Бинарное дерево». Размер 816 КБ. Автор: Admin.

Загрузка...

Бинарное дерево

содержание презентации «Бинарное дерево.ppt»
СлайдТекст
1 Rank-Balanced Trees

Rank-Balanced Trees

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

2 Операции над элементами в деревьях

Операции над элементами в деревьях

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

3 Проблема в бинарных деревьях

Проблема в бинарных деревьях

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

4 Баланс

Баланс

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

5 Повороты

Повороты

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

6 Пример двойного правого поворота

Пример двойного правого поворота

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

7 Повороты

Повороты

Повороты.

8 Balanced Search Trees

Balanced Search Trees

Balanced Search Trees. Binary. Multiway. Red-Black trees AVL trees Weight Balanced trees LLRB trees. 2,3 trees B trees.

9 Самобалансирующееся бинарное дерево поиска

Самобалансирующееся бинарное дерево поиска

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

10 Красно-черное дерево

Красно-черное дерево

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

11 Пример красно-черного дерева

Пример красно-черного дерева

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

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, но они симметричны): C. C. C. y. y. y. A. D. A. D. A. D. z. z. B. B. B. z. Узел у красный. Узел у черный и z — правый. Узел у черный и z — левый.

15 1

1

Red-Black Trees. 1. 2. 3.

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 черный, его правый дочерний узел красный.

24 Red-Black Trees

Red-Black Trees

Red-Black Trees.

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. Пример, когда при удалении может потребоваться не один поворот: После восстановления J, узел M все еще остается несбалансированным. Удаляем L (требуется лево-правый поворот вокруг G). M. M. J. R. J. R. Q. Q. E. L. U. E. L. U. X. X. G. N. T. G. N. T. V. V.

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

AVL vs Red-Black

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

37 АВЛ-деревьев

АВЛ-деревьев

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

38 Преимущества

Преимущества

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

39 Ranks

Ranks

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

40 Ranked Binary Trees

Ranked Binary Trees

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

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 + 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 Вставим a

Вставим a

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

44 Вставим d

Вставим d

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

45 Вставим f

Вставим f

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

46 Вставим

Вставим

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

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

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

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

48 Узел q

Узел q

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

49 Удалим d

Удалим d

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

50 Удалим f

Удалим f

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

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 RB-деревья

RB-деревья

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/ И другие.

55 З а в н и м а н и е

З а в н и м а н и е

З а в н и м а н и е. С п а с и б о.

«Бинарное дерево»
Сайт

5informatika.net

115 тем
5informatika.net > Компьютер > Бинарное дерево.ppt