43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

4931. Русская тяжеловозная порода лошадей 894 KB
  Русская тяжеловозная порода В последние десятилетия для тяжеловозного коннозаводства наступили трудные времена. И почти все проблемы возникли из-за сложившейся в стране экономической ситуации. Тяжеловоз всегда был недорогой лошадью. Раньше, при соц...
4932. Основы теории управления. Конспект лекций 1.92 MB
  Основы теории управления Введение Сигналы управления и возмущения в общем случае могут быть не детерминированные, а случайные, поэтому приходиться прибегать к статистическим методам исследования систем автоматического управления (САУ). Кроме того, ч...
4933. Комплексные системы управления качеством продукции 161 KB
  Успех организации в значительной степени определяется качеством товаром и услуг. Для достижения успеха в своей деятельности организация должна обеспечить конкурентоспособное качество и конкурентоспособную цену. Качество продукции представляет...
4934. Стратегический менеджмент. Опорный конспект лекций 77.17 KB
  Тема 1. Общая характеристика стратегического менеджмента Стратегический менеджмент, его характеристика и связь с другими науками. Сущность стратегического менеджмента. Отличие стратегического управления от оперативного. Э...
4935. Измерение элементов зубчатых колес 424.5 KB
  Цель работы Изучить принцип действия и устройство зубомеров и овладеть методикой измерения размеров элементов зубчатых колес штангензубомером и микрометрическим зубомером. Материальное обеспечение Штангензубомер типа...
4936. Необходимость ИТ-аудита 58.5 KB
  Необходимость ИТ-аудита Аудит — это системный процесс получения и оценки объективных данных об экономических действиях и событиях, устанавливающий уровень их соответствия определенному критерию и предоставляющий результаты заинтересованным поль...
4937. Поиск информации в World Wide Web 255 KB
  Поиск информации в World Wide Web Основные понятия всемирной паутины К основным видам сервиса Интернет относят WWW, электронную почту, группы новостей, чат, FTP, Gopher, Wais, Telnet,IP-телефония и др. Рассмотрим  подробнее  наиболее популярны...
4938. Информационные системы управления бизнесом 338.5 KB
  Цели и задачи дисциплины Цель изучения дисциплины Информационные системы управления бизнесом – формирование у студентов фундаментальных знаний по интеллектуализации производственной деятельности менеджера для малого, среднего и корпоративн...
4939. Создание реляционной БД. Установка связей между таблицами. Работа с данными таблицы 323.5 KB
  Создание реляционной БД. Установка связей между таблицами. Работа с данными таблицы Цель работы: научиться создавать таблицы базы данных в режимах конструктора и таблицыиустанавливать связи между нимиосвоить основные приемы заполн...