Красно-черное дерево является дерево двоичного поиска. Это просто аромат BST, который имеет причудливые версии insert и delete операций, которые реорганизуют дерево по мере их запуска, чтобы дерево никогда не становилось «длинным и жестким». Чем длиннее и строче дерево получает, тем больше он ведет себя как связанный список. В среднем для операций с связанным списком требуется половина списка, который нужно коснуться (или весь список в худшем случае), поэтому время выполнения изменяется линейно (O (n) в количестве элементов n). Когда дерево «густое» или почти сбалансированное, тогда операции намного дешевле (O (log n)) каждый. Красно-черные алгоритмы гарантируют, что дерево остается густым.
Чтобы сделать это конкретным, вот два дерева, которые хранят ключи от A до G. Левые длинны и жесткие. Обратите внимание, как выглядит список. В худшем случае для поиска элемента требуется 4 ключевых сравнения. Дерево справа густое. Ему нужно только 3. Здесь разница небольшая. Для дерева из 1023 элементов для строкового дерева требуется 512 сравнений, а кустов - только 10. Это сила log n.
B _D_
/\ / \
A D B F
/\ /\ /\
C F A C E G
/\
E G
Красно-черное дерево не гарантировано идеально густые (в правильной терминологии «отлично сбалансированы»), но красно-черных правила гарантируют, что он достаточно густой математически строгим образом так, что операция раз изменяются как log n, а не линейно по n.
Гений красно-черных правил заключается в том, что они являются «местными». Во время вставки или удаления, которые нарушают правила, их можно восстановить, отрегулировав только постоянное количество узлов для каждого узла, затронутого операцией. Поэтому они дешевы и довольно просты в реализации.
Тем не менее, когда красно-черные правила верны для всего дерева, можно показать умным математическим доказательством, что оно достаточно густо, как описано выше.
А как насчет карты деревьев? Карта - это функция с доменом, называемым набором ключей K и диапазоном, называемым набором значений V. Для реализации карты дерева каждый узел хранит пару значений ключа <k,v>, где k \in K и v \in V. На рисунках выше (и большинстве презентаций) показаны только клавиши (буквы A-G). На карте, вставка, поиск и удаление работают на этих парах довольно очевидным образом. Например, поиск выполняет поиск ключа с использованием обычного алгоритма BST. Когда ключ найден, значение также найдено, потому что оно находится в одной паре. Это то, что вернулось. В java пара называется Map.Entry. Вы можете проверить это в Java source code.
Я не буду вдаваться в подробности о том, как работают красно-черные правила, потому что я не мог улучшить на the Wikipedia page. Я предполагаю и надеюсь, что вам не хватает «большой картины», поэтому теперь обсуждение будет иметь смысл. Хорошей новостью является то, что почти все языки обеспечивают тщательно проверенную и оптимизированную по производительности реализацию дерева, поэтому знание тайных деталей поворота не требуется. Конечно, если вам интересно и просто хотите знать, имейте это! Поздравления!
Для чего это стоит, лучшие объяснения алгоритмов Coder не всегда самые ясные. Охота вокруг для других, пока вам не понадобится «щелчок».Уважаемые учебники в CS уважаются по одной причине: их объяснения превосходны. Corman and Rivest является признанным фаворитом.