2010-01-13 3 views
0

Я пытаюсь понять, как работают красные черные деревья, предположим, что переход от первого к второму на картинке, я получаю это без каких-либо проблем, после этого, согласно учебным ресурсам, мне нужно сделать локальное исправление на красном узле G. Итак, как исправление на 2-м шаге, G просто окрашивается в черный цвет, чтобы сохранить свойства красно-черного?a red black case question

alt text http://img683.imageshack.us/img683/4929/rb1.jpg

благодаря

ответ

2

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