43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

56015. Запорізька Січ у другій половині ХVІІ ст 42.5 KB
  Мета: Показати статус Запорізької Січі в нових історичних умовах ; підкреслити що на к. Опис Січі з висоти пташиного польоту карта схема.Якою була доля Січі після Андрусівського перемиряробота з картою. Чи брали ви участь у національно-визвольній війні?
56016. Сім кольорів щастя. Виховна година в 4 класі 124.5 KB
  Бо у світі багато чого позначено числом сім: сім днів у тижні сім раз відміряй а раз відріж каже народна мудрість; є сім смертних гріхів які посилаються людині щоб вона їх переборола; а ще є сім чудес світу; а ще від щастя людина буває на сьомому небі; і книга за сімома печатями є і мабуть ще багато чогось іншого позначається числом сім. А ще мені здається є сім кольорів щастя. Ви можете заперечити мені що мовляв щастя не має кольору.
56017. Симфонія перемоги 88.5 KB
  Перше завдання: обрати вірне твердження. музична форма що складається з теми та її модифікованих повторень Перевірка виконаного завдання. правильна відповідь оцінюється учнями Друге завдання: з поданих слів скласти схему за якою пишеться увертюра...
56018. Главный садовод Украины 58.5 KB
  Цель: познакомить учащихся с жизнью известного помолога, знаменитого ученого-селекционера Украины В.Л. Симиренко; воспитывать гордость за соотечественника, любовь к своей стране, стремление трудиться во имя процветания своей Родины.
56019. Подорож сторінками життя і творчості Василя Симоненка 173 KB
  На лебединих крилах материнства він плив по життю, вірив, що яким би важким воно не було, його треба прожити чесно, в праці. І боровся за це. Він і нині живе серед людей своїм правдивим і щирим словом. Лягають квіти до пам`ятника Василя Симоненка.
56021. Дерева та їхнє символічне значення у поезіях Тараса Григоровича Шевченка (за шкільною програмою) 153.5 KB
  Термін символ поняття надзвичайно складне неоднозначне тому його сутність завжди залишалася й залишається для вчених дискусійним питанням. Критичний огляд різноманітних концепцій символу свідчить про те що цей термін зберіг протягом тисячоліть ясність і прозорість свого вихідного значення.
56022. Музичні символи України 107.5 KB
  Мета: показати учням та допомогти їм усвідомити важливе значення музичних творів-пісень, що стали державними та духовними символами українського народу; на прикладі пісень «Молитва за Україну» музика Лисенка...