красно-черное дерево - строительство

Question

Недавно я просматривал деревья поиска и столкнулся с красно-черными деревьями, меня смущает то, что в дереве rb корневой узел должен быть черным, и это нормально, теперь, как я буду решать, принимает ли красный узел входящий узелили черный цвет.

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

[Редактировать] Это, например, если мои ключи {7, 2, 4, 1, 9, 10, 8}

Здесь 7 - корень, и он принимает черный цвет, но какой цвет предполагает 2?Как мы решим это?И как мы решаем, какой цвет принимают другие узлы?

                                  7 - (Black)
                   2                              9
           1                   4        8                    10
        NIL   NIL          NIL  NIL   NIL  NIL            NIL  NIL

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

Спасибо.

Answer 1

Посмотрите лекцию о красно-черных деревьях на открытой учебной программе MIT.

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/

Я нашел их очень полезными.

Теперь, если я правильно помню, вы всегда вставляете новый узел как черный узел, а затем переходите к необходимым исправлениям (перекрашивание и / или повороты)

Answer 2

Входящий узел должен быть окрашен в КРАСНЫЙ, потому что если вы окрашиваете входящий узел в черный цвет, то высота всех путей от листа к корню для вновь вставленного узла будет увеличиваться на единицу, что нарушит свойство дерева RB, которому каждый корень соответствует. Конечный путь должен содержать одинаковое количество черных узлов. Используйте этот параметр, если хотите получить более подробную информацию о вставке дерева RB http://www.youtube.com/watch?v=6QOKk_pcv3U