«Красно-черное дерево»

3. Аналогия с B-деревом порядка 4

То же самое красно-черное дерево, что и в примере выше, представленное как B-дерево.
Красно-черное дерево схоже по структуре с B-деревом порядка 4, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. В таком В-дереве каждый узел будет содержать только одно значение, соответствующее значению черного узла красно-черного дерева с необязательным значениями до и/или после него в том же узле, оба из которых соответствуют эквивалентным красным узлам красно-черного дерева.
Один из способов увидеть эту эквивалентность — «поднять» красные узлы в графическом представлении красно-черного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками черными узлами, образуя страницу. В В-дереве, или в модифицированном графическом представлении красно-черного дерева, у всех листовых узлов глубина одинаковая.
Этот тип В-дерева является более общим, чем красно-черное дерево, хотя, как видно, из одного такого В-дерева порядка 4 могут быть получены несколько красно-черных деревьев. Если страница В-дерева содержит только одно значение, данный узел черный и имеет двух потомков. Если страница содержит три значения, то центральный узел является черным, а каждый его сосед — красным. Однако, если страница содержит два значения, любой узел может стать черным в красно-черном дереве (и тогда второй будет красным).

4. Работа с красно-чёрными деревьями

Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнер map в большинстве реализаций библиотеки STL языка C++^[1], класс TreeMap языка Java^[2], так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.
Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности. В частности, при сравнении с идеально сбалансированными деревьями часто обнаруживается, что последние имеют слишком жесткое условие сбалансированности и при выполнении операций удаления из дерева много времени тратится на поддержание необходимой сбалансированности.