Я ищу руководство, как реализовать удаление элемента в красно-черном дереве без использования фиктивного узла (т.е. листовые узлы на самом деле являются нулевыми указателями). Все реализации, которые я нашел в google/wikipedia и стандартной литературе (sedgewick и cormen и др.), используют фиктивный NIL-узел, которого я хотел бы избежать.
красное черное дерево - удаление элемента без муляжей
Ответы (1)
Для вставки двойное красное устранение Окасаки работает из коробки. Вставьте, как обычно, в BST и продолжайте устранять двойные красные, пока не дойдете до корня.
Удаление красного узла никогда не является проблемой. Обратите внимание, что узел с двумя дочерними элементами никогда не удаляется из BST. Если вы удалите черный узел с одним дочерним элементом, покрасьте его в черный цвет, и все готово. Проблема только в удалении черных листьев (настоящих, а не пустышек). Подход Мэтта Майта можно заставить работать без фиктивных узлов. Хитрость заключается в том, чтобы сначала превратить лист в красный цвет, используя «бульканье» Мэтта. Затем просто удалите его.
Вот решение с код.
person
cayhorstmann
schedule
12.05.2011
