Преимущество сторожевого узла в красном черном дереве?

Question

Я создал двусвязный список, и преимущества дозорного узла были очевидны - никаких нулевых проверок или особых случаев на границах списка.

Сейчас я пишу красное черное дерево и пытаюсь выяснить, есть ли какая-либо польза от такой концепции.

Моя реализация основана на двух последних функциях в этой статье (вставка / удаление сверху вниз). Автор использует "фиктивный корень дерева" или "голову", чтобы избежать особых случаев в корне для его алгоритмов вставки / удаления. Головной узел автора ограничен самими функциями - по-видимому, из-за его ограниченной полезности.

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

Кто-нибудь может уточнить, как сторожевой узел будет полезен в красном черном дереве?

Answer 1

Реализации красно-черного дерева почти всегда используют один черный страж для всех листьев.

Это экономит много пустых проверок, когда вы можете проверить цвет, не проверяя сначала пустое значение.

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