43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

5 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

43029. Проектирование фильтра нижних частот на основе микрополосковой линии 220.5 KB
  Цель работы Целью работы является проектирование фильтра нижних частот на основе микрополосковой линии определение продольных и поперечных величин всех его элементов. Основной задачей будет нахождение наиболее оптимальной модели фильтра удовлетворяющего заданным характеристикам задача синтеза. На первом этапе проектирования рассчитываются число элементов фильтра n и все k = 1 2. Желательно выбрать диэлектрик с возможно более высоким значением εr а высота h подложки влияет на механическую прочность в процессе изготовления сборки...
43030. Разработка базу дискографии музыкальных коллективов 3.57 MB
  Приведение отношения к 3НФ подразумевает, чтобы отношение было нормализовано по 2НФ и в отношении не существовало бы транзитивных зависимостей. Другими словами третья нормальная форма повышает требования второй нормальной формы: оно не ограничивается составными первичными ключами, а требует, чтобы ни один не ключевой столбец не зависел от другого не ключевого столбца. Любой не ключевой атрибут должен зависеть только от первичного ключа.
43031. Усилитель мощности звуковой частоты 956.5 KB
  Усилители низкой частоты являются одним из важнейших структурных элементов звуковоспроизводящих радиотехнических устройств. Развитие усилительных устройств тесно связано с совершенствованием электронных приборов, сначала ламп, затем транзисторов и интегральных микросхем. Резкий скачок в усовершенствовании усилителей произошел после того, как нашла применение отрицательная обратная связь.
43034. Разработка программы вывода графического изображения с помощью языка PostScript 640 KB
  Для обеспечения печати файлов в ОС UNIX имеются специальные средства, позволяющие выводить файлы на печать последовательно, один за другим, организовывать печать на принтерах, подключенных к компьютеру по сети, регламентировать доступ пользователей к различным печатающим устройствам и контролировать объем печати разными пользователями. В ядро ОС включены только драйверы локального принтера, которые передают ему печатаемые данные и следят за его состоянием.
43037. Разработка технологического процесса обработки детали с заданной годовой программой выпуска 106 KB
  10 Расчет технологических размерных цепей эскиз детали 1.11 Расчет припусков на механическую обработку расчетноаналитическим методом на один самый точный размер 1.12 Расчет припусков на механическую обработку по нормативным данным остальные размеры 1.13 Расчет КИМ 1.