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

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

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

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

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

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

3.6. Сильноветвящиеся деревья

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

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

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

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

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

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

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

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

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

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

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