43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

54062. Пригоди веселих кошенят 44.5 KB
  Під музичний супровід діти разом із логопедом заходять до музичної зали. Логопед: Доброго ранку доброго дня Хай плещуть долоньки Хай тупають ніжки Хай ротик співає Та сяють усмішки. Піпіпі куди це я потрапила Логопед.
54063. Логопсихокорекція у роботі з дітьми з порушеннями мовлення 67.5 KB
  Ігри і вправи на розвиток емоційної сфери Казка-гра : Про рибака та рибку Логопед читає уривок з казки О. Гра із шишками напруження та розслаблення мязів рук. Гра з бджілкою напруження та розслаблення мязів ніг. Ведмедиця кличе золоту бджілку погратися з ведмежатами.
54064. Програма логопедичної роботи з дітьми старшого дошкільного віку із ЗНМ III-го рівня 65.5 KB
  Учити виділяти назви предметів дій ознак розуміти узагальнювальне значення слів. Учити дітей перетворювати дієслова наказового способу 2ї особи однини в дієслова дійсного способу 3ї особи однини і множинного числа теперішнього часу спи спить сплять спали спала. Учити дітей використовувати в самостійній мові присвійні займенники мій моя моє у поєднанні з іменниками чоловічого і жіночого роду деяких форм словозміни шляхом практичного оволодіння іменниками єдиного і множинного числа дієсловами єдиного і множинного числа...
54065. Конспект логопедичного заняття: «Хто де живе?» 45.5 KB
  Виховання доброзичливості бажання бути справедливим; Корекційно навчальна: Формувати у дітей навички звязного мовлення: учити складати розповідь за малюнком за запитанням оцінювати розповіді товаришів; управляти в уживанні іменників назв приміщень певного призначення складати речення з прийменниками в по у біля поруч; учити давати відповідь на запитання використовуючи прислівники; Хід заняття 1 Організаційний момент Створення емоційного позитивного настрою на занятті Хто де живе Логопед кидає дітям мяч і починає...
54066. Конспект логопедичного заняття: Зелене царство 82 KB
  Бесіда Рослини поруч з нами Уточнення та розширення словника по темі Логопед. Який світ навколо нас Логопед допомагає дітям дібрати та повторити словаознаки: світ великий красивий багатий яскравий. Логопед.
54067. Интегрированное занятие для детей старшей логопедической группы « А мы идем, шагаем по Земле» 51 KB
  Дерево трава цветок и птица Не всегда умеют защититься Если будут уничтожены они На планете мы останемся одни Приглашаю всех вас в гости Спит девочка. Лучик танцует и нежно будит девочку ДЕВОЧКА: просыпаясь и потягиваясь Доброе утро Какое оно прекрасное Лучику Ой Кто ты ЛУЧИК: Я Лучик Солнца золотой Пришел к тебе с небес...
54068. Дидактичні матеріали до логопедичних занять з теми «Диференціація свистячих і шиплячих». Розрізнення дж-дз 125 KB
  Насупилось небо, плаче хмаринка. А поле сміється щасливо і дзвінко, бо сльози хмаринки несуть урожай. Як сльози ці звуться? Ану відгадай.
54069. Дифференциация звуков с – з. Развитие речи по лексической теме «Зима» 63 KB
  Картинки с изображениями Дети катаются на лыжах Дети катаются на санках Дети катаются на коньках Дети лепят снеговика. Дети повторяют движения за логопедом. Дети по очереди прикасаются к большому пальцу остальными пальчиками в ритме стихотворения. Дети лепят снеговика.
54070. Подолання вад звуковимови й звукосприймання 23.89 MB
  Виправлення недоліків звуковимови проводиться у певній послідовності за прийнятою методикою. Під час цих вправ звертається увага на положення язика: корінь спокійний а кінчик язика біля нижніх різців. Вправи для язика: рухи язиком вперед і назад відкритим ротом як котик...