43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

61176. ВІДОКРЕМЛЕНІ Й НЕВІДОКРЕМЛЕНІ ОЗНАЧЕННЯ, СПОСОБИ ЇХ ВИРАЖЕННЯ 59 KB
  Актуалізація мотиваційних резервів учнів з теми Творче спостереження з елементами аналізу Прочитати виразно текст додержуючись відповідної інтонації в ускладнених реченнях. Назвати речення ускладнені: а однорідними членами; б вставними словами; в відокремленими членами.
61177. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ОЗНАЧЕННЯМИ 203 KB
  Удосконалити в учнів загальнопізнавальні вміння правильно інтонувати речення з відокремленими й невідокремленими означеннями, пунктуаційні вміння й навички, пов’язані з уживанням розділових знаків у реченнях з відокремленими означеннями
61178. ВІДОКРЕМЛЕНІ ПРИКЛАДКИ 327 KB
  Виділити відокремлені прикладки. Алгоритм характеристики відокремленої прикладки Дослідження-трансформація Подані речення трансформувати так щоб виділені компоненти виступали в ролі відокремленої прикладки. Виділити відокремлені прикладки.
61179. ВІДОКРЕМЛЕНІ ДОДАТКИ. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ДОДАТКАМИ 217.05 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з відокремленими додатками, їх місцем у реченні; формувати загальнопізнавальні вміння знаходити в тексті відокремлені додатки, аналізувати їх, правильно інтонувати речення з відокремленими додатками
61180. ВІДОКРЕМЛЕНІ ОБСТАВИНИ, СПОСОБИ ЇХ ВИРАЖЕННЯ 131.02 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з основними способами морфологічного вираження відокремлених обставин, їх місцем у реченні відповідно до опорного слова; формувати загальнопізнавальні вміння знаходити в тексті відокремлені обставини
61181. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ОБСТАВИНАМИ 163.98 KB
  Удосконалити в учнів загальнопізнавальні вміння правильно інтонувати речення з відокремленими обставинами, пунктуаційні вміння й навички, пов’язані з уживанням розділових знаків у реченнях з відокремленими обставинами
61182. ПИСЬМОВИЙ ТВІР-ОПОВІДАННЯ З ОБРАМЛЕННЯМ НА ОСНОВІ ПОЧУТОГО 142 KB
  Довести що висловлювання належить до оповідання. Яку структуру має текст-оповідання Виділити в тексті обрамлення і зясувати яку функцію воно виконує у структурі оповідання. Формування вмінь моделювати твіроповідання з обрамленням Уведення у висловлювання обрамлення Прочитати мовчки текст.
61183. ВІДОКРЕМЛЕНІ УТОЧНЮВАЛЬНІ ЧЛЕНИ РЕЧЕННЯ. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З УТОЧНЮВАЛЬНИМИ ЧЛЕНАМИ 403.78 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з уточнювальними членами речення, їх основними способами морфологічного вираження, видами та значенням; сформувати загальнопізнавальні вміння знаходити в тексті відокремлені уточнювальні члени
61184. УЗАГАЛЬНЕННЯ Й СИСТЕМАТИЗАЦІЯ З ТЕМИ «ВІДОКРЕМЛЕНІ ЧЛЕНИ РЕЧЕННЯ» 503.5 KB
  Правопис: розділові знаки в реченнях з відокремленими членами. Текст риторичний аспект: використання відокремлених членів речення в усному й писемному мовленні. Яку функцію в реченні виконують відокремлені члени речення.