43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

8 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

27523. Политический режим 32 KB
  Политический государственный режим совокупность приемов и способов осуществления политической власти в государстве. Политический режим характеризуется методами осуществления политической власти степенью политической свободы в обществе открытостью или закрытостью элит с точки зрения социальной мобильности фактическим состоянием правового статуса личности. Демократия политический режим при котором единственным источником власти признаётся народ власть осуществляется по воле и в интересах народа.
27524. Понятие и виды норм права 31.5 KB
  Юридическая норма норма права общеобязательное веление выраженное в виде госновластного предписания и регулирующее обществ. Сосредоточены в Конституции; нормыпринципы з датые предписания выражающие и закрепляющие принципы права; определительноустановочные нормы предписания определяющие цели задачи отделх отраслей права правовых институтов предмет формы и средства правового регулирования закрепляющие целевые установки з датля; нормы дефиниции правовые понятия термины: определение преступления виды сделок; б нормы...
27525. Понятие и виды функций права 34.5 KB
  Понятие и виды функций права. Сегодня нет единого взгляда на проблему функции права. Если синтезировать многочисленные точки зрения по этому вопросу то можно увидеть что в конечном счете под функцией права понимают либо социальное назначение права либо направление правового воздействия на общественные отношения либо и то и другое вместе взятое. Система функций права является сложным многоуровневым явлением.
27526. Понятие и классификация нормативно-правовых актов 28 KB
  НПА предписания субъектов правотворчества содержащие нормы права. Признаки НПА: 1 результат правотворческой деятельности органов и должностных лиц наделенных строго определенной компетенцией; 2 содержат общеобязательные правила поведения и предписания; 3 выражают государственную волю; 4 принимаются в особом порядке; 5 имеют установленную форму указ постановление закон реквизиты порядок вступления в силу и сферу действия; 6 регулируют наиболее типичные массовые отношения рассчитаны на постоянное длительное действие; 7 не...
27527. Понятие и структура правосознания 25 KB
  Выделяют следующие основные черты правосознания: 1 является одной из форм общественного знания; 2 состоит из идей теорий чувств эмоций настроений и других компонентов; 3 носителями компонентов правосознания являются различные субъекты права; 4 обращено не только к настоящему но и к прошлому и к будущему; 5 является формой права в отдельные периоды развития общества; 6 ориентирует субъектов права в социальноправовых ситуациях позволяет им делать соответствующий не всегда правомерный выбор и принимать юридически значимые решения....
27528. Понятие, признаки и виды правомерного поведения 29 KB
  Понятие признаки и виды правомерного поведения Правомерное поведение личности это поведение соответствующее предписаниям юридических норм т. законопослушное социальное поведение облеченное в юридическую форму. Правомерное поведение очень широко по своему диапазону и весьма неоднородно по характеру. Активное правомерное поведение.
27529. Понятие, стадии, способы и типы правового регулирования 31.5 KB
  Понятие стадии способы и типы правового регулирования Правовое регулирование целенаправленное результативное юридическое воздействие права на общественные отношения осуществляющееся при помощи совокупности юридических средств норм права правоотношений и актов реализации составляющих его механизм механизм правового регулирования. Метод правового регулирования представляет собой специфический способ совокупность способов правового воздействия на регулируемые общественные отношения. Он складывается из комбинации следующих способов...
27530. Правовая культура, понятие и структура 26 KB
  Правовая культура понятие и структура. Существует несколько подходов к понятию культуры: 1 антропологические согласно которым культура это совокупность всех благ созданных человеком в отличие от того что создала природа; 2 социологические согласно которым культура это совокупность всех духовных ценностей; 3 философские согласно которым культура это исторически определенный уровень развития общества творческих сил и способностей человека. Таким образом правовая культура это совокупность всех ценностей созданных человеком в...
27531. Правовое отношение: понятие и признаки, состав 25 KB
  Правоотношения это охраняемые государством общественные отношения возникающие как правило вследствие воздействия норм права на поведение людей и характеризующиеся наличием субъективных прав и юридических обязанностей у их участников. Признаки: 1 разновидность отношений общественных; 2 возникают на основе норм права; 3 характеризуются наличием у их участников субъективных прав и юридических обязанностей; 4 волевые отношения это означает что помимо нормы права которая сама по себе уже выражает определенную волю для возникновения...