Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Однопроходное добавление элемента в красно-черное дерево

Читайте также:
  1. В появившемся окне Добавление таблицы выделить имя таблицы “Студенты”®Добавить®Закрыть.
  2. В себя соотнесение с элементами, составляющими более
  3. Возможные темы дебатов с элементами политического кейса
  4. ГЛАВА ПЯТНАДЦАТАЯ КАК ПОВАЛИТЬ ДЕРЕВО
  5. Дерево Добра и Зла
  6. Добавление бобышки
  7. Добавление выпадающих меню

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

Итак, все, что нам нужно, это – не допустить реализации случая 1, т.к. случай 3 сводится к случаю 2, а последний завершает алгоритм. Это можно обеспечить, перекрашивая вершины при поиске листа, после которого следует вставить новую вершину. Иными словами, нам следует обеспечить, чтобы либо у вставляемой был бы черный родитель (тогда ничего больше делать не надо), либо у вставляемой вершины был бы черный дядя (тогда дерево можно сделать красно-черным за два поворота).

При поиске листа, после которого следует вставить новую вершину, вы, сначала рассматриваем в качестве текущей вершины p корень дерева. Далее в качестве p рассматриваем один из потомков корня, и т.д. Пусть, для определенности, от вершины p мы переходим к вершине p->left, тогда нам следует обеспечить, чтобы p->right была бы черной вершиной.

Рассмотрим все возможные случаи. Следует рассматривать только случаи, когда оба потомка p красные (легко увидеть, что случаи, когда p->left или p->right – черные нас устраивают).

1.p->par – черный, оба потомка p – красные. Тогда, все, что нужно сделать – перекрасить p и его потомков и перейти к рассмотрению следующей вершины p->left.

 

 

2.p->par – красный, причем p – правый потомок p->par, p->par – левый потомок p->par->par, оба потомка p – красные (случай, когда оба потомка – левые - аналогичен).

Сначала, мы перекрашиваем p и его потомков. Теперь мы попали в ситуацию, аналогичную случаю 2, рассмотренному выше. Как было показано выше, за один поворот и одну перекраску проблему можно решить.

3.p->par – красный, причем p – правый потомок p->par, p->par – левый потомок p->par->par, оба потомка p – красные (случай, когда p – левый потомок p->par, p->par – правый потомок p->par->par - аналогичен).

Сначала, мы перекрашиваем p и его потомков. Теперь мы попали в ситуацию, аналогичную случаю 3, рассмотренному выше. Как было показано выше, за два поворота и одну перекраску проблему можно решить.

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


Дата добавления: 2015-10-30; просмотров: 115 | Нарушение авторских прав


Читайте в этой же книге: Struct SQueue | Стандартная ссылочная реализация списков | InsertData( value, head, current); | Реализация L2-списка на основе двух стеков | Поиск пути в графе с наименьшим количеством промежуточных вершин | Поиск кратчайшего пути в графе | Добавление элемента | Сбалансированные и идеально сбалансированные бинарные деревья поиска | Добавление элемента в дерево | Разбиение дерева по разбивающему элементу |
<== предыдущая страница | следующая страница ==>
Добавление элемента в красно-черное дерево| Удаление элемента из красно-черного дерева

mybiblioteka.su - 2015-2024 год. (0.006 сек.)