43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

16915. Работа с несколькими листами в OpenOffice.org Calc 89.5 KB
  Лабораторные работы № 18Работа с несколькими листами Оборудование: ПК Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Задание: 1. Запустить OpenOffice.org Calc. 2. Вычислить объем продаж в магазине То
16916. Решение практических задач в Windows EXCEL 53 KB
  Лабораторная работа № 1920 Решение практических задач. Оборудование: ПЭВМ Программное обеспечение: Windows EXCEL. Цель работы: приобретение и закрепление практических навыков работы в EXCEL Логические функции в EXCEL: ЕСЛИ Условие; Выражение
16917. Создание базы данных в Windows, Access 70 KB
  Лабораторная работа № 21 Создание базы данных Оборудование: ПЭВМ Программное обеспечение: Windows Access. Цель работы: приобретение и закрепление практических навыков работы в Access Общие характеристики MS Access. Структура базы данных Система управления базами
16918. Создание простых запросов в Windows, Access 73.5 KB
  Лабораторная работа № 22 Создание простых запросов. Оборудование: ПЭВМ Программное обеспечение: Windows Access Цель работы: приобретение и закрепление практических навыков работы в Access Выбор записей отвечающих определенному условию можно осуществить как с
16919. Создание реляционной базы данных. Разработка инфологической модели и создание структуры реляционной базы данных 133.5 KB
  Разработка инфологической модели и создание структуры реляционной базы данных Для разработки инфологической информационно-логической модели базы данных выделим три объекта: Студенты Дисциплины и Преподаватели. Типы связей между этими
16920. Формирование сложных запросов в Windows, Access 86 KB
  Лабораторная работа № 2425 Формирование сложных запросов Оборудование: ПЭВМ Программное обеспечение: Windows Access Цель работы: приобретение и закрепление практических навыков работы в Access Задание 1. Формирование сложных запросов Создайте следующие зап
16921. Программируемый контроллер прямого доступа к памяти КР580ВТ57 2.84 MB
  ЛАБОРАТОРНАЯ РАБОТА №5 Программируемый контроллер прямого доступа к памяти КР580ВТ57 Методические указания Цель работы: Знать функциональные возможности программируемого контроллера прямого доступа к памяти КР580ВТ57 логику его работы и способы подключения ег...
16923. ТРИ СТАТЬИ ПО ТЕОРИИ СЕКСУАЛЬНОСТИ 813 KB
  ТРИ СТАТЬИ ПО ТЕОРИИ СЕКСУАЛЬНОСТИ Издательство Алетейя г. СПб 1998 г. ПРЕДИСЛОВИЕ АВТОРА К 3му ИЗДАНИЮ Наблюдая в течение десятилетия за тем как была встречена эта книга и какое впечатление она произвела я хотел бы предпослать третьему изданию несколько за...