43988

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

Доклад

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

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

Русский

2014-03-31

15.01 KB

5 чел.

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

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

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

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

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

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

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

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

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

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

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

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


 

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

83858. Хирургическая анатомия лёгких. Корень лёгкого 45.58 KB
  Сегмент участок легкого вентилируемый бронхом третьего порядка. На медиальной поверхности каждого легкого располагаются его ворота. Здесь находятся составляющие корень легкого анатомические образования: бронх легочные артерии и вены бронхиальные сосуды и нервы лимфатические узлы. Скелетотопически корень легкого располагается на уровне VVII грудных позвонков.
83859. Хирургическая анатомия полости груди. Техника пункции и дренирование плевральной полости 50.76 KB
  Техника пункции и дренирование плевральной полости. В грудной полости располагаются три серозных мешка: два плевральных и один перикардиальный. Между плевральными мешками в грудной полости расположено средостение в котором помещается комплекс органов куда входят сердце с перикардом грудная часть трахеи главные бронхи пищевод сосуды и нервы окруженные большим количеством клетчатки.
83860. Хирургическая тактика при проникающем ранении груди. Торакотомия. Обработка лёгочных артерий, лёгочных вен и бронхов 54.15 KB
  Гемоторакс скопление крови в полости плевры в результате повреждения кровеносных сосудов или стенки сердца. Диагностику проводят рентгенологически и с помощью пункции плевральной полости. Гемопневмоторакс скопление крови и воздуха в плевральной полости. Пневмоторакс скопление воздуха в плевральной полости в результате повреждения плевры.
83861. Лечение пневмоторакса 50.16 KB
  при повреждении париетальной плевры: внутренний при ране лёгкого или повреждении бронха т. при повреждении висцеральной плевры. закрытый однократное попадание воздуха и разобщение полости плевры с атмосферой; открытый постоянное сообщение плевральной полости с атмосферным воздухом во время вдоха воздух через рану проникает в плевральную полость а при выдохе выходит наружу: клапанный поступление воздуха только в плевральную полость изза наличия клапана нарастающее накопление воздуха в плевральной полости. Этапы помощи при...
83862. Долевое и сегментарное строение лёгких. Трахея и главные бронхи. Особенности лёгочных артерий и лёгочных вен 282.9 KB
  Длина трахеи 915 см ширина 1527 см. Место разветвления трахеи на два бронха получило название бифуркации трахеи. С внутренней стороны место разделения представляет собой вдающийся в полость трахеи полулунный выступ – киль трахеи. Главные бронхи асимметрично расходятся в стороны: правый более короткий 3 см но более широкий отходит от трахеи под тупым углом над ним залегает непарная вена; левый бронх длиннее 45 см более узкий и отходит от трахеи почти поп прямым углом над ним проходит дуга аорты.
83863. Резекция лёгкого. Хирургическая тактика при раке и доброкачественных опухолях лёгкого 50.4 KB
  Техника резекции лёгкого заднебоковой доступ; пневмолиз выделение из сращений; вскрытие медиастиналыюй плевры; обработка корня: последовательно вначале артерию затем вену и в конце бронх при раке вену артерию бронх; удаление легкого; проверка герметичности культи бронха физраствор в плевральную полость смотрят наличие пузырьков воздуха при раздувании; дренаж в плевральную полость; ушивание раны. Радикальные операции на легких выполняют при раке легкого туберкулезе легких бронхоэктатической болезни хронической пневмонии...
83864. Пункция перикарда и ушивание раны сердца. Техника выполнения 46.5 KB
  Пункция перикарда Показания: с диагностической или лечебной целями преимущественно при выпотных перикардитах. Ушивание раны сердца оперативный доступ обычно по ходу раневого канала; продольное вскрытие перикарда широким разрезом кпереди от диафрагмального нерва; наложение узловых или Побразных швов на рану; освобождение полости перикарда от сгустков крови; ушивание перикарда редкими швами.
83865. Коронарные артерии и проводящая система сердца. Принципы операций на коронарных артериях, шунтирование и стентирование 54.08 KB
  Коронарные артерии . interventriculris posterior – конечная ветвь правой коронарной артерии проходит в одноимённой борозде; r. interventriculris posterior конечная ветвь левой коронарной артерии проходит в одноимённой борозде.
83866. Хирургическая анатомия пищевода. Операции на пищеводе 66.98 KB
  Хирургическая анатомия пищевода Отделы: шейный грудной и брюшной. Синтопия: Спереди пищевода лежат перстневидный хрящ и трахея; сзади позвоночник и длинные мышцы шеи: по бокам нижние полюсы боковых долей щитовидной железы и общие сонные артерии. Правый возвратный нерв проходит позади трахеи по боковой поверхности пищевода.