Страницу Назад
Поискать другие аналоги этой работы
750 Построение красно-черных деревьевID: 159098Дата закачки: 08 Ноября 2015 Продавец: evelin (Напишите, если есть вопросы) Посмотреть другие работы этого продавца Тип работы: Работа Лабораторная Форматы файлов: C++ Сдано в учебном заведении: ******* Не известно Описание: Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n). Красно-черное дерево - это бинарное дерево с следующими свойствами: 1) Каждый узел покрашен либо в черный, либо в красный цвет. 2) Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет. 3) Если узел красный, то оба его потомка черны. 4) На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково. Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум - когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем - узлы при этом покрашены (от корня к листу) так: красный, черный, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться. Комментарии: 1. Общие теоретические ведомости 2. Алгоритм решения 3. Структура программы 4. Листинг программы 5. Порядок работы с программой Размер файла: 438 Кбайт Фаил: (.rar)
Скачано: 1 Коментариев: 0 |
||||
Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них. Опять не то? Мы можем помочь сделать! Некоторые похожие работы:К сожалению, точных предложений нет. Рекомендуем воспользоваться поиском по базе. |
||||
Не можешь найти то что нужно? Мы можем помочь сделать! От 350 руб. за реферат, низкие цены. Спеши, предложение ограничено ! |
Вход в аккаунт:
Страницу Назад
Cодержание / Программ. обеспеч. цифр. систем коммутации / Построение красно-черных деревьев
Вход в аккаунт: