Структуры данных и модели вычислений

       

черного дерева красный. Если мы


  1. Предположим, что корень красно- черного дерева красный. Если мы покрасим его в черный цвет, останется ли дерево красно-черным?
  2. Покажите, что самый длинный путь вниз от вершины к листу не более чем вдвое длиннее самого короткого такого пути.
  3. Какое наибольшее и наименьшее количество внутренних узлов может быть в красно-черном дереве черной высоты?

Вращения — это манипуляции с красно-черными деревьями с целью восстановления RB-свойств в случае их нарушения. Их используют при реализации операцийи. Вращение представляет собой локальную операцию, при которой меняется несколько указателей, но свойство упорядоченности сохраняется.
На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.

Рис. 10.1. 
Левое вращение возможно в любом узле, правый ребенок которого (назовем его ) не является листом (). После вращения оказывается корнем поддерева,— левым ребенком узла, а бывший левый ребенок— правым ребенком узла .

Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий