43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

38516. Створення культурно розважального сайту міста Хмельницького 3.73 MB
  Виходячи з даних проблем у роботі даного вебсайту має бути розроблений сайт про культурно розважальне життя міста Хмельницького з усіма його подіями розважальними закладами та коротким описом. В ході дипломногопроетування було створено вебсай за допомогою якого користувачі можуть переглядати різні заклади для відпочинку а також різноманітні розважальні заходи що відбудуться у цих закладах чи інші події у місті Хмельницькому 1 Характеристика предметної області. Розглянемо похожі вебсайти на наявність переваг та недоліків.
38517. Раскрытие юридического механизма действия уголовно-правовой нормы об убийстве, совершенном при превышении пределов необходимой обороны 467 KB
  Равно как и тесно связанный с ним являющийся как бы его частью институт превышения пределов необходимой обороны.37 УК РФ не является преступлением причинение вреда посягающему лицу при защите личности и прав обороняющегося или других лиц интересов общества или государства от общественно опасного посягательства если при этом не допущено превышения пределов необходимой обороны. Стало быть превышение пределов необходимой обороны – действие преступное.
38518. Общие сведения работы на предприятии, санитарно-технические требования и пошаговое приготовление блюд (Борщ и куриные котлеты на косточке) 845 KB
  Исторически борщ — это национальное блюдо Древнего Рима, где специально для него выращивали много капусты и свеклы. Из Рима этот прекрасный суп постепенно проник в кулинарии многих народов мира, в каждой из них приобретая свои особенные национальные черты.
38519. Разработка базы данных «Кредитование клиентов» 430 KB
  Одной из постоянных проблем персональных компьютеров является нехватка памяти. Как правило, персональный компьютер мы используем в ежедневной работе, учебе, отдыхе, играх. Поэтому очень важно, чтобы ваш ПК имел достаточное количество памяти для хранения различного рода информации
38520. Разработка дизайн-проекта актового зала ГБОУ СПО (ССУЗ) «Златоустовский Металлургический колледж» а с учетом эргономических требований 20.98 MB
  Сначала роль электрической лампочки выполняли обычные свечи рисунок 1 позже им на смену пришел керосин рисунок 2 потом появились газовые фонари рисунок 3. Рисунок 1 – Свеча Рисунок 2 – Керосиновая лампа Рисунок 3 – Газовый фонарь Кованые фонари издавна использовались не только как средство освещения улицы или помещения но и как красивое украшение. Рисунок 4 Кованый фонарь Рисунок 5 Кованые фонари Рисунок 6 ...
38522. Технологічний процес виробництва НАД (нікотинамідаденіндинуклеотиду) 1.51 MB
  Складено аналітичний огляд літератури щодо властивостей сучасних лікарських форм та галузей застосування коферментів. завдяки сучасним біотехнологіям отримало надзвичайні можливості щодо вирішення соціальних проблем пов’язаних з харчуванням зростаючого населення планети підтримкою здоров’я людини і навколишнього середовища поповненням джерел енергії та природних ресурсів [1]. Стан біотехнологічної галузі потребує великої уваги з боку держави тому що роль сучасної біотехнології є вирішальною для становлення економіки...
38523. РИСК И ПРИ ОПЕРАЦИЯХ С НЕДВИЖИМЫМ ИМУЩЕСТВОМ 128.5 KB
  1 РИСК И ПРИ ОПЕРАЦИЯХ С НЕДВИЖИМЫМ ИМУЩЕСТВОМ В операциях с недвижимостью риск может проявляться в более низкой чем планировалось ранее цене при продаже недвижимости; в более высоком чем предполагалось уровне операционных расходов при управлении недвижимости; в снижении фактической рентабельности инвестиционного проекта по сравнению с проектной и даже в утрате собственности как в связи с разрушением самого тела недвижимости так и по причине потери прав на недвижимость. Целесообразно рассмотреть общую классификацию рисков...
38524. Електропостачання виробничого цеху деревообробного комбінату ТОВАРИСТВА «ДНІПРОВУД» 1.77 MB
  Потужність двигунів коливається від 55 до 37 кВт. При напрузі розподільної мережі 10 кВ двигуни середньої потужності 3501000 кВт потрібно використовувати на напругу 6 кВ з використанням в необхідних випадках схеми блоку трансформатордвигун при невеликій кількості двигунів на 6 кВ.1 – Відомість електричних приймачів цеху Номер на плані Найменування електроприймачів Кількість Рн кВт соsφ tgφ Кв 1 Верстат багатопильний 1 37 065 117 017 28 Лінія форматної обробки 2 55 05 17 014 3 Лінія для вирізання сучків 1 66 06 13 016 4...