Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 9 )

Если balance==-1, то узел «перевешивает влево», т. к. высота левого поддерева больше, чем высота правого поддерева. При положительном balance узел «перевешивает вправо». Сбалансированный по высоте узел имеет balance==0. В AVL-дереве показатель сбалансированности должен быть в диапазоне [-1, 1].

Включение в сбалансированное дерево

Преимущество AVL-деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки-удаления.

Процесс включения является почти таким же, как и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым наследникам, пока не встретится пустое поддерево, а затем производится пробное включение нового узла в этом месте.

1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве.

2. Включить новый узел и определить новый показатель сбалансированности.

3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.

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

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balance равен 0). После включения в поддерево нового элемента узел стал перевешивать влево или вправо, в зависимости от того, в какое поддерево было произведено включение. Если элемент был включен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, - то 1.

До включения узла 55

После включения узла 55

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел включается в более легкое поддерево. Узел становится сбалансированным.

До включения узла 55

После включения узла 55

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел включается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balance выходит за пределы -1 ... 1. Чтобы восстановить равновесие, нужно выполнить поворот.

Повороты

Повороты необходимы, когда родительский узел P становится разбалансированным. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному повороту двух или трех узлов. Кроме вращения ссылок, следует также изменить соответствующие показатели сбалансированности узлов.

Одинарный поворот вправо происходит тогда, когда родительский узел P и его левый потомок LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым наследником. Бывшее правое поддерево узла LC (ST) присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворот уравновешивает как родителя, так и его левого потомка.

Пример:

Исходное дерево	Показатели сбалансированности до поворота
После поворота	Попытка включить узел 5 в AVL-дерево нарушает AVL-условие для узла 30 и выводит его из равновесия. Одновременно левое поддерево узла 15 (LC) становится перегруженным. Для переупорядочения узлов вызывается одинарный поворот вправо. В результате родительский узел (30) становится сбалансированным, а узел 10 - перевешивающим влево.

Двойной поворот вправо происходит тогда, когда родительский узел (P) становится перевешивающим влево, а его левый потомок (LC) - перевешивающим вправо. NP - корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

Возможны два варианта:

Вставка узла в левое поддерево узла NP

Вставка узла в правое поддерево узла NP

Пример:

Попытка включить узел 25 разбалансирует корневой узел 50. В этом случае узел 20 (LC) приобретает слишком высокое правое поддерево и требует двойной поворот. Новым родительским узлом (NP) становится узел 40. Старый родительский узел становится его правым наследником и присоединяет к себе узел 45, который также переходит с левой стороны дерева.

Удаление из сбалансированного дерева

Удаление из сбалансированного дерева основано на алгоритме удаления элемента из дерева с учетом операции балансировки, которая состоит из однократного или двукратного поворота узлов.

Удаление ключа 4 само по себе просто, так как он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного поворота налево.

При удалении узла 8 балансировки не требуется. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня сбалансируется однократным поворотом направо. При удалении узла 5 балансировка не требуется.

Удаление узла 2 вызывает сложный двукратный поворот направо и налево.

Ценность AVL-деревьев зависит от приложения, поскольку они требуют дополнительных затрат на поддержание сбалансированности при включении или исключении узлов. Если в дереве постоянно происходят вставки или удаления элементов, эти операции могут значительно снизить быстродействие. С другой стороны, если данные превращают бинарное дерево поиска в вырожденное, то теряется поисковая эффективность.

Сложность операции поиска для AVL-деревьев составляет. Опыт показывает, что повороты требуются примерно в половине случаев включений и удалений. Сложность балансировки обусловливает применение AVL-деревьев только там, где поиск является доминирующей операцией.

Лекция №12

Тема: Сильноветвящиеся деревья

Цель: познакомить с  Б-деревьями и  Бинарными Б-деревьями

Если узлы дерева имеют более двух потомков, то такие деревья принято называть сильноветвящимися. При описании таких деревьев правильно было бы расположить потомство в виде линейного списка со ссылкой в записи родителей на самого младшего (старшего) потомка.

Возможное описание типа для такого случая имеет следующий вид:

struct TREE{
  int dann;
  TREE *ps;
  TREE *pn;
  };

Алгоритмы, работающие с такими структурами, тесно связаны с их описанием, поэтому нельзя для них определить общие правила или методы работы.

Сильноветвящиеся деревья нашли широкое применение при организации банков данных, систем управления базами данных.

Такие структуры часто преобразуют в бинарные деревья для упрощения алгоритмов их обработки, а также используются в виде Б-деревьев для организации страничного доступа в крупномасштабных деревьях поиска.

Алгоритм преобразования произвольного дерева с упорядоченными узлами в бинарное дерево:

1. В каждом узле исходного дерева вычеркиваем все ветви, кроме самой левой ветви, которая соответствует ссылке на старшего сына.

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

3. В получившемся дереве левым (старшим) сыном каждого узла Х считается непосредственно находящийся под ним узел (если он есть), а в качестве правого (младшего) сына - соседний справа брат для Х (если таковой есть).

Переход от произвольного дерева к его бинарному эквиваленту не только облегчает анализ логической структуры, но также и упрощает машинное представление, т. е. физическую структуру дерева.

Б-деревья

Важная область применения сильноветвящихся деревьев - формирование и использование крупномасштабных деревьев поиска, которые хранятся не в оперативной памяти, а на внешнем запоминающем устройстве (например, на диске).

В отличие от деревьев в оперативной памяти, в данном случае ссылки представляют собой не адреса оперативной памяти, а адреса на диске (номера записи в файле).

Сильноветвящиеся деревья позволяют организовать память таким образом, что требуется наименьшее число обращений к диску за счет того, что можно обратиться сразу к группе элементов дерева.

Структурно это можно представить следующим образом:

Дерево разделено на поддеревья, называемые страницами (в данном случае на каждой странице 7 узлов).

Однако при организации сильноветвящихся деревьев необходима схема управления их ростом.

Разумный критерий был сформулирован Р. Бэйером для структур данных, называемых Б-деревьями:

1. Каждая страниц содержит не более 2n элементов (n - порядок Б-дерева).

2. Каждая страница, кроме корневой, содержит не менее n элементов.

3. Каждая страница является либо листом, т. е. не имеет потомков, либо имеет m+1 потомков, где m - число находящихся на ней ключей.

4. Все листья находятся на одном и том же уровне.

Б-дерево второго порядка с тремя уровнями:

Все страницы содержат 2, 3, 4 элемента. Корню разрешается иметь только один элемент. Все листья находятся на уровне 3. Ключи расположены в возрастающем порядке слева направо. Если потомков вставить между ключами на странице-предке, то порядок не нарушится.

Поиск по Б-дереву

Пусть задан аргумент поиска х.

Предположим, что оперативную память считана какая-то страница Б-дерева

где - ключи; - указатели на страницы-потомки.

Если m достаточно велико, то можно применить бинарный поиск, если оно небольшое, то можно применить и последовательный поиск.

Возможны следующие ситуации:

x = = , искомый элемент найден. для 1 ? i < m. Продолжаем поиск на странице. . Продолжаем поиск на странице. . Продолжаем поиск на странице. Если ссылка равна NULL, то элемента с таким ключом нет во всем дереве.

Для представления Б-дерева в оперативной памяти можно выбрать следующую структуру: