43988

Выбор и обоснование структуры данных для алгоритма построения красно-черного дерева

Доклад

Информатика, кибернетика и программирование

Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева

Русский

2014-03-31

15.01 KB

6 чел.

Выбор и обоснование структуры данных для алгоритма построения красно-черного дерева.

Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n).

Прекрасно написанные разделы о красно-черных деревьях вы найдете у Кормена-Ривеста-Лейзертона в их талмуде об алгоритмах.

Красно-черное дерево - это бинарное дерево с следующими свойствами:

Каждый узел покрашен либо в черный, либо в красный цвет.

Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет.

Если узел красный, то оба его потомка черны.

На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

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

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

Вот пять правил для построения красно-черного дерева:

  1. Каждый узел должен быть или красным или черным.
  2. Корень дерева должен быть черным.
  3. Листья дерева(концевые узлы) должны быть черными.
  4. Каждый красный узел должен иметь черного предка.
  5. Каждый путь от некоторого узла к какому-либо листу должен содержать одинаковое число черных узлов.
  6. Ни один путь от узла к корню не превышает другого пути более чем вдвое. Это конечно не полная балансировка, но ее вполне достаточно для большинства случаев. А различные операции вставки и удаления, использующие правила 4 и 5 гораздо более эффективны, чем аналогичные использующие полную балансировку.


 

А также другие работы, которые могут Вас заинтересовать

7466. Информатизация общества, понятие информации и системы управления 136.5 KB
  Тема 1 Информатизация общества, понятие информации и системы управления 1. Информация и различные аспекты ее обработки 2. Система и системный подход в управлении Измерение производительности - способ оценки возможностей страны обеспечить повыше...
7467. Метрологическое обеспечение на этапах жизненного цикла продукции 36.5 KB
  Тема 1.1 Метрологическое обеспечение на этапах жизненного цикла продукции Студент должен иметь представление: - о роли и значении метрологического обеспечения в управление качеством продукции - об отражении треб...
7468. Метрологическая экспертиза технической документации 51.5 KB
  Тема 1.2 Метрологическая экспертиза технической документации Студент должен иметь представление: - о необходимости метрологической экспертизы технической документации знать: - порядок метрологической экспертизы т...
7469. Метрологическое обеспечение технологического процесса изготовления продукции 71 KB
  Тема 1.3 Метрологическое обеспечение технологического процесса изготовления продукции Студент должен иметь представление: - о необходимости метрологического обеспечения средств измерений, обеспечивающих стабильность технологическо...
7470. Рулевое управление ВАЗ 2121 62 KB
  Рулевое управление ВАЗ 2121 Рис. Рулевое управление. 1. Боковая тяга 2. Сошка 3. Средняя тяга 4. Маятниковый рычаг 5. Регулировочная муфта 6. Нижний шаровой шарнир подвески 7. Поворотный кулак 8. Верхний шаровой шарнир подвески 9. Подшипник ...
7471. Исследование напряженно-деформированного состояния элементов составных балок 9.79 MB
  Исследование напряженно-деформированного состояния элементов составных балок Введение Балки являются одним из самых употребляемых строительных элементов любых зданий и сооружений. По своей статической схеме балки представляют конструкцию, как правил...
7472. Исследование электромеханических свойств двигателя постоянного тока последовательного возбуждения 108.09 KB
  Исследование электромеханических свойств двигателя постоянного тока последовательного возбуждения. Цель работы: Исследовать способы регулирования скорости вращения и реверсирования якоря двигателя, построить рабочие характеристики двигателя. Пояснен...
7473. Снятие кривой нагрева электродвигателя и определение постоянной времени нагрева 63.24 KB
  Снятие кривой нагрева электродвигателя и определение постоянной времени нагрева. Цель работы: Изучить процесс нагрева двигателя, получить опытным путем данные построения кривой нагрева электродвигателя и определить значение постоянной времени нагрев...
7474. Исследование трехфазного асинхронного двигателя 55.54 KB
  Исследование трехфазного асинхронного двигателя Цель работы: Экспериментально снять механическую характеристику трехфазного асинхронного двигателя и осуществить его реверс. Пояснения к работе: Для выполнения данной работы используют трехфазный асинх...