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

         

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


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

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

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

Содержание  Назад  Вперед