23:41 АВЛ-дерево | |
| [править | править вики-текст] Материал из Википедии — свободной энциклопедии Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 14 декабря 2015; проверки требуют 9 правок. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 14 декабря 2015; проверки требуют 9 правок. Перейти к: навигация, поиск Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. АВЛ-дерево Тип дерево поиска Изобретено в 1962 году Изобретено Адельсон-Вельский Георгий Максимович и Ландис Евгений Михайлович Временная сложность в О-символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича. Содержание [скрыть] 1 Максимальная высота 2 Балансировка 3 Алгоритм добавления вершины 4 Алгоритм удаления вершины 5 Нерекурсивная вставка в АВЛ-дерево сверху-вниз 6 Нерекурсивное удаление из АВЛ-дерева сверху вниз 7 Расстановка балансов при удалении 8 Расстановка балансов при одинарном повороте 9 Расстановка балансов при двойном повороте 10 Оценка эффективности 11 См. также 12 Примечания 13 Литература Максимальная высота[править | править вики-текст] Максимальная высота АВЛ-дерева при заданном числе узлов [1]: h ≤ ⌊ 1.45 log 2 ( n + 2 ) ⌋ {\displaystyle h\;\leq \;\lfloor 1.45\log _{2}(n+2)\rfloor \;} Количество возможных высот на практике сильно ограничено (при 32-битной адресации максимальная высота равна 45, при 48-битной — 68), поэтому лучше заранее подсчитать все возможные значения минимального количества узлов для каждой высоты с помощью рекуррентной формулы для дерева Фибоначчи: n 0 = 0 {\displaystyle n_{0}=0} , n 1 = 1 {\displaystyle n_{1}=1} , n h = n h − 2 + n h − 1 + 1 {\displaystyle n_{h}=n_{h-2}+n_{h-1}+1} . Промежуточные значения количества узлов будут соответствовать предыдущей (меньшей) высоте. Балансировка[править | править вики-текст] Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины. Используются 4 типа вращений: Малое левое вращение Данное вращение используется тогда, когда высота b-поддерева — высота L = 2 и высота С <= высота R. Большое левое вращение Данное вращение используется тогда, когда высота b-поддерева — высота L = 2 и высота c-поддерева > высота R. Малое правое вращение Данное вращение используется тогда, когда высота b-поддерева — высота R = 2 и высота С <= высота L. Большое правое вращение Данное вращение используется тогда, когда высота b-поддерева — высота R = 2 и высота c-поддерева > высота L. В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться. Также можно заметить, что большое левое вращение это композиция правого малого вращения и левого малого вращения. Из-за условия балансированности высота дерева О(log(N)), где N- количество вершин, поэтому добавление элемента требует O(log(N)) операций. Алгоритм добавления вершины[править | править вики-текст] Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основываться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Никлаусом Виртом в «Алгоритмы и структуры данных»): Прохода по пути поиска, пока не убедимся, что ключа в дереве нет. Включения новой вершины в дерево и определения результирующих показателей балансировки. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка. Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к hl < hr: выравняется hl = hr. Ничего делать не нужно. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется. hl > hr: теперь hl — hr = 2, — требуется балансировка. В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево. Алгоритм удаления вершины[править | править вики-текст] Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1. Очевидно, что в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по второму вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций. Становится очевидной возможность оптимизации: поиск ближайшей вершины может быть выполнен по краю поддерева, что сокращает сложность до O(log(N)). Нерекурсивная вставка в АВЛ-дерево сверху-вниз[править | править вики-текст] Нерекурсивный алгоритм сложнее рекурсивного. Находится место вставки и вершина, высота которой не изменится при вставке (это вершина, у которой высота левого поддерева не равна высоте правого; будем называть её PrimeNode) Выполняется спуск от PrimeNode до места вставки с изменением балансов Выполняется ребалансировка PrimeNode при наличии переполнения Нерекурсивное удаление из АВЛ-дерева сверху вниз[править | править вики-текст] Для реализации удаления будем исходить из того же принципа, что и при вставке: найдём вершину, удаление из которой не приведёт к изменению её высоты. Существует два случая: высота левого поддерева равна высоте правого поддерева (исключая случай, когда у листа нет поддеревьев) высота дерева по направлению движения меньше противоположной(«брат» направления) и баланс «брата» равен 0 (разбор этого варианта довольно сложен, так что пока без доказательства) Для облегчения понимания приведённый алгоритм не содержит каких-либо оптимизаций. В отличие от рекурсивного алгоритма, найденная удаляемая вершина заменяется значением из левой подветви. Этот алгоритм можно оптимизировать так же, как и рекурсивный (за счёт того, что после нахождения удаляемой вершины известно направление движения): ищем удаляемый элемент и попутно находим нашу замечательную вершину производим изменение балансов, в случае необходимости делаем ребалансировку удаляем наш элемент (в действительности не удаляем, а заменяем его ключ и значение, учёт перестановок вершин будет немного сложнее) Расстановка балансов при удалении[править | править вики-текст] Как уже говорилось, если удаляемая вершина — лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист — ей находится «замена», и обратный обход дерева происходит от родителя «замены». Непосредственно после удаления элемента — «замена» получает баланс удаляемого узла. При обратном обходе: если при переходе к родителю пришли слева — баланс увеличивается на 1, если же пришли справа — уменьшается на 1. Это делается до тех пор, пока при изменении баланса он не станет равным −1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке. Расстановка балансов при одинарном повороте[править | править вики-текст] Обозначим: «Current» — узел, баланс которого равен −2 или 2: то есть тот, который нужно повернуть (на схеме — элемент a) «Pivot» — ось вращения. +2: левый сын Current’а, −2: правый сын Current’а (на схеме — элемент b) Если поворот осуществляется при вставке элемента, то баланс Pivot’а равен либо 1, либо −1. В таком случае после поворота балансы обоих устанавливаются равными 0. При удалении всё иначе: баланс Pivot’а может стать равным 0 (в этом легко убедиться). Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Pivot: Направление поворота Old Pivot.Balance New Current.Balance New Pivot.Balance Левый или Правый -1 или +1 0 0 Правый 0 -1 +1 Левый 0 +1 -1 Расстановка балансов при двойном повороте[править | править вики-текст] Pivot и Current — те же самые, но добавляется третий участник поворота. Обозначим его за «Bottom»: это (при двойном правом повороте) левый сын Pivot’а, а при двойном левом — правый сын Pivot’а. При данном повороте — Bottom в результате всегда приобретает баланс 0, но от его исходного баланса зависит расстановка балансов для Pivot и Current. Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Bottom: Направление Old Bottom.Balance New Current.Balance New Pivot.Balance Левый или Правый 0 0 0 Правый +1 0 -1 Правый -1 +1 0 Левый +1 -1 0 Левый -1 0 +1 Оценка эффективности[править | править вики-текст] Из формулы, приведённой выше, высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших n {\displaystyle n} имеет место оценка 1.04 log 2 n {\displaystyle 1.04\log _{2}{n}} . Таким образом, выполнение основных операций требует порядка log 2 n {\displaystyle \log _{2}{n}} сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые 2 включения и на каждые 5 исключений. См. также[править | править вики-текст] Сбалансированные (самобалансирующиеся) деревья: Красно-чёрное дерево Матричное дерево Идеально сбалансированное дерево Расширяющееся дерево Примечания[править | править вики-текст] ↑ Д. Кнут. Искусство Программирования. Сортировка и Поиск. — С. 460. Литература[править | править вики-текст] Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — С. 272—286. Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263—266. Ben Pfaff. GNU libavl [показать] Дерево (структура данных) Двоичное дерево поиска Дерево (теория графов) Древовидная структура Двоичные деревья Двоичное дерево T-дерево Самобалансирующиеся двоичные деревья АА-дерево АВЛ-дерево Красно-чёрное дерево Расширяющееся дерево Дерево со штрафами Декартово дерево Дерево Фибоначчи B-деревья B-дерево 2-3-дерево B+-дерево B*-дерево UB-дерево 2-3-4 дерево (a,b)-дерево Танцующее дерево Префиксные деревья Суффиксное дерево Базисное дерево Ternary search tree Двоичное разбиение пространства k-мерное дерево VP-дерево Недвоичные деревья Дерево квадрантов Октодерево Sparse Voxel Octree Экспоненциальное дерево PQ-дерево Разбиение пространства R-дерево R+-дерево R*-дерево X-дерево M-дерево Дерево Фенвика Дерево отрезков Другие деревья Куча TTH Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree LSM-Tree Алгоритмы Поиск в ширину Поиск в глубину DSW-алгоритм Алгоритм связующего дерева Источник — «https://ru.wikipedia.org/w/index.php?title=АВЛ-дерево&oldid=86870037» Категории: ИнформатикаДеревья (структуры данных)Скрытая категория: Википедия:Статьи к переработке | |
|
| |
| Всего комментариев: 0 | |