![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Удаление из сбалансированного дерева
Удаление из сбалансированного дерева основано на алгоритме удаления элемента из дерева с учетом операции балансировки, которая состоит из однократного или двукратного поворота узлов.
Удаление ключа 4 само по себе просто, так как он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного поворота налево.
Ценность AVL -деревьев зависит от приложения, поскольку они требуют дополнительных затрат на поддержание сбалансированности при включении или исключении узлов. Если в дереве постоянно происходят вставки или удаления элементов, эти операции могут значительно снизить быстродействие. С другой стороны, если данные превращают бинарное дерево поиска в вырожденное, то теряется поисковая эффективность. Сложность операции поиска для AVL -деревьев составляет 3.6. Сильноветвящиеся деревья Если узлы дерева имеют более двух потомков, то такие деревья принято называть сильноветвящимися. При описании таких деревьев правильно было бы расположить потомство в виде линейного списка со ссылкой в записи родителей на самого младшего (старшего) потомка. Возможное описание типа для такого случая имеет следующий вид: struct TREE{ Алгоритмы, работающие с такими структурами, тесно связаны с их описанием, поэтому нельзя для них определить общие правила или методы работы. Сильноветвящиеся деревья нашли широкое применение при организации банков данных, систем управления базами данных. Такие структуры часто преобразуют в бинарные деревья для упрощения алгоритмов их обработки, а также используются в виде Б-деревьев для организации страничного доступа в крупномасштабных деревьях поиска. Алгоритм преобразования произвольного дерева с упорядоченными узлами в бинарное дерево: 1. В каждом узле исходного дерева вычеркиваем все ветви, кроме самой левой ветви, которая соответствует ссылке на старшего сына. 2. В получившемся графе соединяем горизонтальными ветвями те узлы одного уровня, которые являются братьями в исходном дереве. 3. В получившемся дереве левым (старшим) сыном каждого узла Х считается непосредственно находящийся под ним узел (если он есть), а в качестве правого (младшего) сына - соседний справа брат для Х (если таковой есть).
Переход от произвольного дерева к его бинарному эквиваленту не только облегчает анализ логической структуры, но также и упрощает машинное представление, т.е. физическую структуру дерева.
|