Я пытаюсь присоединиться к двум красно-черным деревьям в O (m + n).Я понял алгоритмическую логику этого процесса, но у меня все еще проблемы с цветами узлов.
У меня есть вектор, в котором есть все узлы (все черные), упорядоченные по их ключу.Я использую обход Inorder, чтобы построить Красное Черное Дерево.В то же время я хочу покрасить красные узлы, которые должны быть самыми глубокими в дереве.
Я уже провел некоторое исследование и нашел, что кто-то говорит: «Обратите внимание, когда вы разбиваете массивклавиш пополам, две половинки имеют либо одинаковое количество клавиш, либо они различаются на единицу. Когда они имеют одинаковое количество клавиш, назначать цвета легко. Когда их нет, вам может потребоваться использовать некоторыекрасные узлы ... "
Проблема в том, что я не имею никакого представления о том, какие узлы я должен окрашивать в красный цвет.Может кто-нибудь помочь мне?