Что, если дядя черный, а родитель черный при вставке узла в красное черное дерево?
Я знаю, что есть два случая, когда дядя становится черным в красно-черных деревьях при вставке нового узла. Но во всех случаях родитель красный. если родитель черный, нарушения нет. что мне делать в такой ситуации на красном черном дереве?
1 ответ
Если вы в конечном итоге добавляете узел в красно-черное дерево, а его родительский элемент становится черным, вы можете просто сделать узел красным и назвать его днем. Там нет необходимости каких-либо исправлений. Если вы посмотрите на правила для красных / черных деревьев, это не вызовет каких-либо новых нарушений, потому что все пути root-null все еще проходят через одинаковое количество черных узлов.
Другая точка зрения: если вы думаете о красных / черных деревьях как об изометрии или 2-3-4 деревьях, то это правило соответствует тому, что нужно взять лист с одним ключом и добавить другой, что не требует дополнительной фиксации шаги.