Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2019-11-19 | 283 |
5.00
из
|
Заказать работу |
В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает разбалансировка поддерева. Для выправления ситуации применяются повороты вокруг тех или иных узлов дерева.
См. вопрос про вставку узлов, там всё есть
Оценка сбалансированных деревьев
Обоснованность применения AVL-деревьев неоднозначна, поскольку они требуют дополнительных затрат на поддержание сбалансированности при вставке или удалении узлов. Если в дереве постоянно происходят вставки и удаления элементов, эти операции могут значительно снизить быстродействие. С другой стороны, если ваши данные превращают бинарное дерево поиска в вырожденное, вы теряете поисковую эффективность и вынуждены использовать AVL-дерево. В большинстве случаев в программах используются алгоритмы, когда сначала заполняется список, а потом производится поиск по этому списку с небольшим количеством изменений. Поэтому на практике использование AVL-деревьев предпочтительно.
Для AVL-дерева не существует наихудшего случая, так как оно является почти полным бинарным деревом. Сложность операции поиска составляет O(log2n). Опыт показывает, что повороты требуются примерно в половине случаев вставок и удалений. Сложность балансировки обусловливает применение AVL-деревьев только там, где поиск является доминирующей операцией.
Из формулы, приведенной в начале этого вопроса, высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших n имеет место оценка 1,04log2n. Таким образом, выполнение основных операций требует порядка log2n сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые 2 включения и на каждые 5 исключений.
Красно-чёрные деревья и их свойства
Красно-черное дерево – это еще одна форма сбалансированного бинарного поискового дерева. Время поиска, вставки или удаления узла для красно-черного дерева является логарифмической функцией от числа узлов.
Данный тип деревьев отличается от других реализаций следующими свойствами:
- каждый узел ассоциируется с определенным цветом - красным или черным;
- корневой узел может быть любого цвета;
- красные узлы могут иметь только черные дочерние узлы;
- все пути от узла до любого листа, расположенного ниже в дереве, содержат одно и то же количество черных узлов.
Высота красно-черного дерева, состоящего из N узлов, лежит в диапазоне от двоичного логарифма log(N+1) до 2 * log(N+1).
Варианты вставки узла в красно-чёрное дерево
При вставке нового узла в красно-черное дерево для него изначально устанавливается красный цвет. Затем для добавляемого элемента выполняется поиск родительского узла и проверка его цвета. Если цвет родителя черный, то основной критерий цветного дерева сохраняется. Если же родитель - красного цвета, то выполняется итеративная (нерекурсивная) балансировка дерева. В худшем случае время вставки может достичь значения логарифма от числа узлов в красном дереве.
Для упрощения алгоритма предполагается, что листья (узлы, не имеющие потомков) имеют черный цвет.
В общем случае при вставке нового узла возможны три варианта.
- происходит изменение цвета;
- требуется сделать один поворот;
- требуется сделать двойной поворот.
Для этого в памяти кроме текущего узла нужно хранить еще три уровня дерева: «родителя», «деда» и «прадеда» текущего узла.
Варианты удаления узла из красно-чёрного дерева
При удалении узла из цветного дерева цвет родительского узла не изменяется. Удаление красного узла не влечет никаких последствий, коллизию может вызвать только удаление узла черного цвета. Поэтому при удалении черного узла для обеспечения целостности дерева необходимо использовать различные операции: простую смену цвета (если это возможно) или одну или несколько ротаций. Ниже представлены 4 ситуации, возможных при удалении черного узла.
Если при удалении черного узла, его «брат» (узел, находящийся на том же уровне, что и удаляемый) и все их четыре потомка имеют черный цвет (это вариант I на рисунке 2), то выполняется изменение цвета.
Если «брат» удаляемого узла окрашен в красный цвет, то производится ротация, изображенная на варианте II.
Если удаляемый узел и его «брат» черного цвета, а правый потомок «брата» - красного, то выполняется двойная ротация, изображенная на варианте 4.
Если левый потомок «брата» красного, то выполняется одиночная ротация, как в пятом варианте.
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!