Докажите, что красно-черное дерево остается в силе после превращения множества S в красные узлы черного цвета

Question

В настоящее время я ломаю голову над следующим вопросом: Докажите, что в красно-черном дереве T, если каждый путь от корня до листа содержит хотя бы один красный узел, мы можем выбратьнабор красных узлов в T для окрашивания в черный цвет, так что T остается действительным красно-черным деревом, а высота черного увеличивается на единицу.потерял даже старт

Answer 1

Самый простой способ подумать об этом - подтолкнуть красные узлы вверх по дереву, а затем снова повернуть корень черного цвета.

Представьте себе дерево, похожее на следующее:

       B
  R        B
 B   B  R  B
B B B B B B R R

Если естьэто красный узел на каждом пути, тогда будет хотя бы один черный узел с двумя красными дочерними элементами.Если вы подтолкнете красный узел вверх по дереву в каждой позиции, где это происходит, начиная с нижней части, в конечном итоге вы подтолкнете красный узел к корню дерева, и в этот момент вы сможете перевернуть цвет, и высота дерева вырастет на единицу.

Кроме того, если вы когда-либо достигнете конфигурации, где весь уровень будет красным, все узлы на этом уровне можно будет перевернуть, не изменяя свойств дерева, и снова высота увеличится на единицу.

Это несколькоХитрее, если в некоторых путях имеется более одного красного узла, в этом случае вам нужно работать с самого верхнего красного узла в этом пути и выдвинуть красный узел из другой ветви, чтобы сопоставить его.