Структуры данных и модели вычислений
черного дерева красный. Если мы
- Предположим, что корень красно- черного дерева красный. Если мы покрасим его в черный цвет, останется ли дерево красно-черным?
- Покажите, что самый длинный путь вниз от вершины к листу не более чем вдвое длиннее самого короткого такого пути.
- Какое наибольшее и наименьшее количество внутренних узлов может быть в красно-черном дереве черной высоты?
Вращения — это манипуляции с красно-черными деревьями с целью восстановления RB-свойств в случае их нарушения. Их используют при реализации операцийи. Вращение представляет собой локальную операцию, при которой меняется несколько указателей, но свойство упорядоченности сохраняется.
На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.
Рис. 10.1.
Левое вращение возможно в любом узле, правый ребенок которого (назовем его ) не является листом (). После вращения оказывается корнем поддерева,— левым ребенком узла, а бывший левый ребенок— правым ребенком узла .
