43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

5 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

23594. Общенаучный метод моделирования и специфика его применения в лингвистике 11 KB
  Моделью можно назвать образ какоголибо объекта используемый в определенных условиях в качестве его заместителя фотография в паспорте модель человека. Свойства моделей: условность образ может быть не только материальным но и мысленным и передаваться посредством знаковой системы моделью может быть не только образ но и праобраз оригинала модель чаще всего является гомоморфной оригиналу то есть многим элементам оригинала соответствует меньшее количество элементов модели в отличие от изоморфизма Модель в лингвистике искусственно...
23595. Синтез речи 30.5 KB
  1 Ограничения на синтез речи. Cуществуют различные методы синтеза речи. Возможности синтезированной речи зависят от того в какой области она будет применятся.
23596. Типы лингвистических моделей; основные требования к ним и критерии их оценки 12.5 KB
  по гносеологическому статусу: модели языка модели лингвистических знаний различные фонетические школы модели деятельности лингвиста 4. по отраженному аспекту языка и речевой деятельности: Модели различаются не только по направленности на определенный объект но и по используемым средствам моделирования алгоритму или исчислению Алгоритм строгая последовательность предписывающих правил Исчисление множество разрешающих правил порядок выполнения не важен анализирующие модели моделируют процесс понимания используют логическое средство...
23597. Синтаксический анализ 184 KB
  При использовании синтаксического анализа происходит интерпретация отдельных частей высказывания а не всего высказывания в целом. Деревья анализа и свободноконтекстные грамматики. Большинство способов синтаксического анализа реализовано в виде деревьев. Свободноконтекстная грамматика широко используется в машинных языках и с ее помощью созданы высокоэффективные методы анализа.
23598. Метаязыки формального описания семантических структур 17.5 KB
  Метаязыки формального описания семантических структур. Семантические метаязыки различаются: по объекту который они описывают морфема лексема словосочетание предложение текст в целом. по аспекту языковой структуры который они отражают: парадигматический аспект синтагматический аспект Сходимость МЯ возможность переводить с одного МЯ на другой. значение словосочетаний исследуется в парадигматическом аспекте при помощи тех же МЯ описания что и лексемы в синтагматическом плане: язык лексических параметров и функций Апресян понятие...
23599. Автоматизация анализа письменного текста: основные подходы к решению проблемы 16 KB
  ТБД автоматизированная система инвентаризации и машинного представления терминологической лексики и ее семантизации в системах машинного и человекомашинного речевого общения. Научные задачи: моделирование терминологической системы РЯ как системы подсистем построение общенаучных и общетеоретических тезаурусов исследование русской терминологии Типы традиционного использования ТБД: справочноинформационное обслуживание специалистов различных областей знания обеспечение традиционного перевода научнотехнической литературы обеспечение АСОТ...
23600. Когнитивная лингвистика и ее основные исследовательские программы 19.5 KB
  Когнитивная лингвистика и ее основные исследовательские программы. Когнитивная наука некий раздел научного знания центральное понятие которого знание и репрезентация исследовательская дисциплина изучающая устройство человеческого сознания используя различные способы репрезентации и компьютерную метафору совокупность современных эмпирических знаний направленных на поиск ответов на давние эпистимологические вопросы особенно о природе знания Когнитивная лингвистика подход который допускает в лигвитсике применение методов когнитивной...
23601. Понимание речи 32.5 KB
  Системы понимания речи СПР имеют дело со связанными единицами речи такими как фразы предложения и даже параграфы так как понимание изолированных слов может означать только тривиальный процесс сопоставления некоторого значения к каждому слову словаря системы. Понимание связанной речи очень сложная задача и на проект СПР повлияли исследования в таких разных областях как акустическая обработка сигнала нейрофизиология психолингвистика психология. СПР была создана чтобы понимать всего нескольких дикторов одного диалекта производя...
23602. Автоматический морфологический анализ. Соотношение словаря и анализа 12.5 KB
  Автоматический морфологический анализ. Соотношение словаря и анализа. Автоматический морфологический анализ АМА анализ отдельно взятой словоформы и всех тех сведений которые из нее можно извлечь безотносительно к тому относятся ли эти сведения к морфологии или нет. АМА определяется двумя факторами: 1 тип ЕЯ подвергаемого анализу 2 тип алгоритма авт.