красное черное дерево - удаление элементов без сосок

Question

Я ищу руководство, как реализовать удаление элемента в красно-черном дереве без использования фиктивного узла (т. Е. Листовые узлы фактически являются нулевыми указателями).Все реализации, которые я нашел в google / wikipedia и в стандартной литературе (sedgewick и cormen at al), используют фиктивный NIL-узел, которого я хотел бы избежать.

Answer 1

Для вставки, двойное красное устранение Окасаки работает из коробки. Вставьте как обычно в BST и продолжайте устранять двойные красные, пока не дойдете до корня.

Удаление красного узла никогда не является проблемой. Обратите внимание, что никто никогда не удаляет узел с двумя дочерними элементами из BST. Если вы удалите черный узел с одним дочерним элементом, закрасьте дочерний черный, и все готово. Только удаление черных листьев (настоящих, а не чайников) является проблемой. Подход Мэтта Мейта можно заставить работать без фиктивных узлов. Хитрость заключается в том, чтобы сначала превратить лист в красный цвет, используя «пузырение» Мэтта. Затем просто удалите его.

Здесь - решение с кодом.