Красно-черные деревья 12
Красно-черные деревья – еще один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева.
Красно-черное дерево - это бинарное дерево со следующими свойствами:
Каждый узел дерева покрашен либо в черный, либо в красный цвет.
Листьями объявляются nil-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" nil указатели). Листья покрашены в черный цвет.
Если узел красный, то оба его потомка черны.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу.
Все вышеперечисленные свойства должны сохраняться при вставке элементов в дерево и удалении из него.
Вставка
Чтобы вставить узел, необходимо сначала найти соответствующее место в дереве. Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL-узлами и предполагаются черными. После вставки необходимо окрасить узел в красный цвет. После этого необходимо проверить все вышеприведенные свойства для его предка. Далее в случае необходимости осуществляется перекрашивание узла и/или поворот, чтобы сбалансировать дерево.
Вставив красный узел с двумя NIL-потомками, свойство черной высоты (свойство 4) сохранится. Однако при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черны. В нашем случае оба потомка нового узла черны по определению (поскольку они являются NIL-узлами), так что необходимо рассмотреть ситуацию, когда предок нового узла красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:
Красный предок, красный "дядя". Данную ситуацию иллюстрирует рис. 17. У нового узла X предок и "дядя" оказались красными. В данном случае простое перекрашивание избавляет от нарушения свойства 3. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным. Следует обратить внимание на то, что в данном случае меняется цвет корня дерева, т.к. в противном случае нарушилось бы свойство черной высоты.
Рис. 17. Вставка – Красный предок, красный дядя
Красный предок, черный "дядя". На рис. 18 представлен другой пример нарушения свойства 3 красно-черных деревьев. В данном случае для коррекции необходимо применить дополнительно вращение узлов. Следует обратить внимание, что если узел X был в начале правым потомком, то для коррекции следует применять левое вращение, которое делает этот узел левым потомком.
Рис. 18. Вставка – красный предок, черный дядя