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


Упражнения


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

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

На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.


Рис. 10.1. 

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




Начало  Назад  Вперед



Книжный магазин