Ссылка на файл: >>>>>> http://file-portal.ru/Красно черное дерево c/
Красно-чёрное дерево (RB-дерево)
Красно-черные деревья
Красно-чёрное дерево
Пусть нам надо реализовать множество или нагруженное множество , на элементах которого определен линейный порядок. Тогда элементы множества или пары ключ, значение в случае нагруженного множества можно расположить в вершинах бинарного дерева. При этом значения в вершинах должны быть упорядочены следующим образом: Для такого дерева можно применять алгоритм бинарного поиска, аналогичный поиску в упорядоченном массиве. Поэтому подобные деревья называют деревьями поиска. Пример дерева поиска приведен на рисунке; его вершины содержат целые значения. Опишем более подробно устройство дерева поиска. Каждая вершина дерева представляет собой следующую структуру: Указатель на элемент множества или на пару ключ, значение содержится в поле value, сам элемент расположен в динамической памяти. В некоторых реализациях value может содержать сам элемент, а не указатель на него. В большинстве алгоритмов удобно считать, что у любой вершины v дерева есть родительская вершина. Корень непустого дерева является левым сыном вершины header. Всюду ниже мы будем считать, что используется заголовочная вершина header, левым сыном которой является корень дерева. Запишем на псевдокоде алгоритм поиска в дереве. Мы ищем элемент x в поддереве с корнем root. Выходной параметр node является указателем на указатель на вершину. Алгоритм возвращает целое значение, которое является результатом последнего выполненного сравнения: Считаем для определенности, что элементы множества имеют тип E. Число сравнений в данном алгоритме не превышает высоты дерева h. Таким образом, время работы алгоритма равно O h. Добавление элемента к упорядоченному дереву легко реализуется с помощью алгоритма поиска. Сначала применяется описанный выше алгоритм find. Если вершина найдена, то в случае обычного множества ничего делать не надо; в случае нагруженного множества надо лишь изменить нагрузку элемента. Для простоты мы ограничимся в дальнейшем случаем обычного множества. Если элемент не содержится в дереве, то алгоритм find находит вершину, которая должна стать родительской для новой вершины. Новая вершина, содержащая добавляемый элемент множества, становится левым или правым сыном найденной вершины в зависимости от величины добавляемого элемента в сравнении с элементом в родительской вершине. Для определения того, каким сыном должен стать новый узел, используется значение последнего сравнения, которое возвращается алгоритмом find. Запишем на псевдокоде алгоритм insert добавления вершины после выполнения поиска. Алгоритмы поиска минимального и максимального элементов используются в алгоритме обхода вершин дерева в соответствии с их упорядоченностью. Для поиска минимальной вершины начинаем с корня поддерева и спускаемся от текущей вершины к ее левому сыну, пока таковой имеется. Алгоритм заканчивается, когда у текущей вершины левого сына нет. Отметим, что минимальная вершина дерева не обязательно должна быть терминальной, у нее может быть правый сын. Выпишем на псевдокоде алгоритм поиска минимальной вершины. Для упорядоченного дерева очень важен алгоритм обхода вершин в соответствии с их порядком. Обход начинается с вершины, содержащей минимальное значение. Затем находим вершину, содержащую следующее значение, и так далее. Алгоритм заканчивается, когда очередной вершиной является "заголовочная" вершина header родитель для корня дерева. Для обхода используется алгоритм nextNode , который по данному указателю на вершину node находит указатель на вершину, содержащую следующее значение. Отметим, что для максимальной вершины дерева следующей является "заголовочная" вершина header. Алгоритм реализуется очень просто: Наконец, если оба эти условия не выполняются, то есть node есть правый сын своего отца и у него нет правого сына, то в цикле идем вверх по дереву, пока текущий узел является правым сыном своего отца. После цикла текущий узел является левым сыном своего отца. Возвращаем ссылку на отца. Приведенные ниже рисунки иллюстрируют три эти случая. Буквой V обозначена текущая вершина, буквой N — вершина, которая содержит следующее значение. Отметим, что алгоритм нигде не использует сравнения значений, содержащихся в вершинах дерева. Алгоритм previousNode , который по указателю на вершину дерева находит указатель на предыдущую вершину, реализуется аналогично. Рассмотрим произвольное дерево поиска. В худшем случае время работы алгоритма поиска равняется длине максимального пути от корня дерева к терминальной вершине, то есть высоте дерева. Для того, чтобы поиск выполнялся по возможности быстрее, дерево должно иметь минимальную высоту при заданном числе вершин. Для этого нужно, чтобы все возможные пути к терминальным вершинам имели бы примерно одинаковую длину более точно, для любой вершины дерева число вершин в ее левом и правом поддеревьях почти совпадали. Перейдем к строгим определениям. Удобно считать, что у каждой вершины дерева есть ровно два сына. Для этого добавим к дереву внешние , или нулевые вершины. Если у какой-либо вершины дерева отсутствует левый или правый сын, то добавляем внешнюю вершину и считаем ее левым или правым сыном соответственно. Для терминальных вершин добавляются два внешних сына. Внешние вершины будем также называть листьями. Обычные вершины дерева будем называть собственными вершинами, причем слово "собственные" иногда будем опускать. Добавление внешних вершин к дереву показано на рисунке. Внешние вершины нулевые вершины, листья изображены прямоугольниками серого цвета, внутри которых написано слово Null, символизирующее нулевой указатель. Длиной пути от корня дерева к внешней вершине будем называть число собственных вершин этого пути то есть последняя внешняя вершина не считается. Дерево называется сбалансированным , или полным , если длины всех путей от корня к внешним вершинам равны между собой. Дерево называется почти сбалансированным , если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Число собственных вершин в сбалансированном дереве высоты h равно 2 h Число вершин произвольного дерева не превосходит числа вершин сбалансированного дерева той же высоты. Для высоты h произвольного дерева, содержащего n вершин, справедливо неравенство: Эффективность реализации множества с помощью дерева поиска зависит от текущей высоты дерева, так как при выполнении большинства операций сначала происходит поиск элемента, а время работы алгоритма поиска пропорционально высоте. При заданном числе вершин n наименьшую высоту имеет сбалансированное или почти сбалансированное дерево последнее в случае, когда n не равно 2 h Однако в случае произвольного дерева время поиска может в худшем случае линейно равняться n если дерево вытянуто в прямую линию. Поэтому при добавлении элементов к множеству желательно перестраивать дерево так, чтобы сохранялось то или иное свойство, близкое к сбалансированности. Это гарантирует быстрое выполнение поиска. Пусть h — высота дерева. Поэтому число n всех вершин дерева не меньше, чем число вершин сбалансированного поддерева. По предложению 1, число вершин сбалансированного поддерева высоты l равно 2 l Для таких деревьев время поиска логарифмически зависит от числа вершин:. В практическом программировании константы в оценке времени работы алгоритма не очень важны — существенна лишь зависимость времени работы от n. Логарифмическая зависимость — наилучшая из всех возможных, поэтому в классе почти сбалансированных деревьев с баланс-фактором C поиск выполняется за оптимальное время. Можно показать, что при добавлении случайных элементов к дереву поиска с помощью рассмотренного выше алгоритма, в котором новая вершина добавляется как терминальная после выполнения поиска родительской вершины, сбалансированность "в среднем" сохраняется, то есть с большой вероятностью баланс-фактор не будет превышать, скажем, двух. Тем не менее существует несколько схем модификации деревьев после добавления и удаления вершин, при которых баланс-фактор всегда будет ограничен при любом сценарии добавления. Наиболее популярны два класса сбалансированных деревьев: AVL-деревья и красно-черные деревья. AVL-деревья названы так в честь двух авторов, впервые предложивших их: Каждая вершина AVL-дерева хранит дополнительно разность высот ее левого и правого поддеревьев, причем эта разность в AVL-дереве может принимать лишь три значения: Можно показать, что для AVL дерева длина максимального пути корня к внешнему листу не превышает константы 1. Более точно, баланс-фактор для достаточно больших n не превышает квадратного корня из двух. Следовательсно, поиск в AVL-деревьях осуществляется за логарифмическое время. Класс AVL-деревьев исторически был первым примером использования сбалансированных деревьев. В настоящее время, однако, более популярен класс красно-черных деревьев. В красно-черных деревьях для балансировки используются цвета вершин. Каждая вершина красно-черного дерева окрашена либо в черный, либо в красный цвет, причем выполняются следующие условия:. Последнее свойство означает сбалансированность красно-черного дерева по черным вершинам. Количество черных вершин на пути от корня дерева к внешней вершине иногда называют черной высотой красно-черного дерева, последнее свойство означает, что определенная таким образом черная высота не зависит от конкрентого пути. Для удобства описания алгоритмов мы будем считать также, что все внешние вершины окрашены в черный цвет, а заголовочная вершина дерева та, которая является родительской для корня дерева — в красный. Пример красно-черного дерева приведен на рисунке. Черные вершины изображаются кружками серого цвета, красные вершины — белого. Пусть h b — черная высота красно-черного дерева, то есть количество черных вершин в произвольном пути от корня дерева к внешней вершине не включая саму внешнюю вершину. По определению красно-черного дерева, эта величина определена корректно не зависит от пути. Поскольку любой путь от корня к внешней вершине начинается с черной вершины в красно-черном дереве корень всегда черный и не может содержать двух красных вершин подряд у красной вершины дети обязательно черные , то длина любого пути не превосходит 2 h b. С другой стороны, длина минимального пути к внешней вершине не меньше чем h b. Таким образом, в случае красно-черного дерева для длин m 0 и m 1 минимального и максимального путей к внешним вершинам выполняются неравенства. Таким образом, красно-черное дерево является почти сбалансированным с баланс-фактором 2. Из предложения 5 вытекает логарифмическая оценка на высоту h красно-черного дерева, содержащего n вершин: Поиск элемента в красно-черном дереве осуществляется за логарифмическое время: При добавлении нового элемента к красно-черному дереву мы сначала применяем обычный алгоритм добавления вершины к дереву поиска, который был рассмотрен выше алгоритм insert. Новая вершина она в рассмотренном алгоритме всегда является терминальной окрашивается в красный цвет. Если родительская вершина для добавленной имеет черный цвет, то все свойства красно-черного дерева при этом сохраняются, и никаких дополнительных действий не требуется. Однако, если родительская вершина красная, то нарушается требование того, что дети красной вершины должны быть черными, и нужно выполнить процедуру восстановления структуры красно-черного дерева. Обычно эта процедура называется восстановлением баланса или ребалансировкой. В алгоритме ребалансировки с деревом совершаются локальные действия, не меняющие упорядоченности его вершин. Действия бывают двух типов:. По рисункам видно, что оба преобразования не меняют упорядоченности вершин дерева. Преобразования носят локальный характер, при их выполнении меняется лишь фиксированное число ссылок в вешинах дерева вблизи вершины, которая "вращается" влево или вправо. Запишем на псевдокоде процедуру вращения вершины x влево. Операция левого или правого вращения вершины во многих случаях позволяет "исправить" балансировку дерева, как показывает следующий пример. В нем мы применяем вращение вершины x влево. В процедуре ребалансировки рассматриваются 6 различных случаев. В случаях отец узла x является левым сыном своего отца, то есть деда x. Случаи зеркально симметричны случаям , в них отец узла x является правым сыном своего отца, то есть деда x. Рассматриваются они аналогично случаям заменой слова "левый" на "правый" и обратно, так что мы их описывать не будем. Укажем, какие действия выполняются в каждом из случаев для восстановления балансировки дерева. Цикл завершается, либо когда мы достигли корня дерева если корень был перекрашен в красный цвет, то надо перекрасить его обратно в черный , либо когда отец узла x черный. Этот случай сводится к случаю 3 путем следующих преобразований: В этом случае выполняются следующие действия: На этом алгоритм восстановления балансировки заканчивается в случае 3 цикл завершается. В этой процедуре выполняются перекрашивание узлов дерева и операции вращения, причем общее число вращений — не больше двух одно вращение в случае 3 и два в случае 2.
Яндекс перевод с итальянского на русский
Практическая работа составление сравнительной экономико географической характеристики
Таблица менделеева основное
Красно-черное дерево
Фирма влади харьков каталог
Питание мамы после перенесения диареи у ребенка
Элементный и групповой состав нефти
Красно-чёрные деревья (С#)
Метро сургут каталог акции сургут
Ведущим компонентом в структуре личности является
Красно-черные деревья
Сколько калорий в тушеном курином филе
26 маршрутка маршрут на карте
Расписание автобуса 250 теплый стан
Красно-черные деревья
Таблица площади сечения провода