Красно-черные деревья
Мы видели, что основные операции с двоичным поисковым деревом высоты могут быть выполнены за действий. Деревья эффективны, если их высота мала, но если не принимать специальные меры при выполнении операций, малая высота не гарантируется, и в этом случае деревья не более эффективны, чем списки.
Для повышения эффективности операций используют различные приемы перестройки деревьев, чтобы высота дерева была величиной. Такие приемы называются балансировкой деревьев. При этом используются разные критерии качества балансировки. Одним из видов сбалансированных деревьев поиска являются так называемые красно-черные деревья, для которых предусмотрены операции балансировки, гарантирующие оценку высоты величиной.
Частным случаем такой балансировки является АВЛ-балансировка, при которой у каждого узла высота его левого поддерева отличается от высоты правого не более чем на единицу. Заметим, что наихудшими в некотором смысле АВЛ-деревьями являются деревья Фибоначчи, определяемые следующим образом:— пустое дерево,— дерево, состоящее из одного узла. При деревосостоит из корня с левым поддеревоми правым —. Нетрудно видеть, что при заданной величине деревоимеет наименьшее число узлов среди всех АВЛ-деревьев высоты .
Для удобства поисковые деревья будем расширять, вводя дополнительный фиктивный узел (-узел) и считая его потомком каждого узла исходного дерева, у которого нет правого, левого или обоих потомков, его же считаем родителем корня.
Красно-черное дерево — это расширенное двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black) так, что:
- Каждый узел либо красный, либо черный.
- Каждый лист (-узел) — черный.
- Если узел красный, то оба его ребенка черные.
- Все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных узлов.
Свойства 1-4 называют RB-свойствами. Узлы красно-черного дерева будем представлять записями вида
