Что означает красность узлов?

Красная вершина в дереве – «лишняя» с точки зрения высоты, то есть поддерево выше чем оно должно быть. RB-дерево обязано выдерживать одинаковое расстояние от всех листьев до корня, но если считать только чёрные вершины. Красные вершины нужны чтобы расслабить требования на балансировку. Поскольку запрещено иметь две последовательные красные вершины, их количество в пути к одному листу не может быть больше половины высоты. Из этого вытекает свойство что кратчайший путь может отличаться от длиннейшего не больше чем в два раза.

«RB-дерево обязано выдерживать одинаковое расстояние от всех листьев до корня, но если считать только чёрные вершины. … Поскольку запрещено иметь две последовательные красные вершины, их количество в пути к одному листу не может быть больше половины высоты. Из этого вытекает свойство что кратчайший путь может отличаться от длиннейшего не больше чем в два раза.»

Вот это не надо было переписывать. Мне этот текст ничего не дал.

«Красная вершина в дереве – «лишняя» с точки зрения высоты, то есть поддерево выше чем оно должно быть. … Красные вершины нужны чтобы расслабить требования на балансировку.»

Это были хорошие слова, но пока их мало. Чего-то нехватает. Можно ли записать математически, когда вершина красная?

цель топика не в том, чтобы вы (читатели форума) изложили своё правильное понимание, а чтобы моё (неправильное) исправилось.

Вершина красная тогда, когда у узла более 2 потомков.

В бинарном дереве более 2-х прямых потомков не бывает никогда. А если считать непрямых, тогда у крупного дерева вся вершина была бы красной (а это не так).

Красные узлы могут иметь только черные дочерние узлы;

При вставке нового узла в красно-черное дерево для него изначально устанавливается красный цвет.
Затем для добавляемого элемента выполняется поиск родительского узла и проверка его цвета.
Если цвет родителя - черный, то все остается как есть.
Если же родитель - красного цвета, то выполняется итеративная (нерекурсивная) балансировка дерева.
В худшем случае время вставки может достичь значения логарифма от числа узлов в красном дереве.

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

В бинарном дереве более 2-х прямых потомков не бывает никогда.

У нас не бинарное дерево, а красно-черное. В нем у узлов может быть от 2 до 4 потомков.

«Красные» узлы подчиняются корневому узлу aka надзиратель. В «чёрных» узлах власть держится на горизонтальных связях между паханами. Как-то так.

ну и что?

Это духота. Просто храни всё в векторе.

Мне этот текст ничего не дал.

Очень жаль, в нем говорится насколько сильно и почему они расслабляют балансировку.

Можно ли записать математически, когда вершина красная?

Ну, на самом деле, цвета это иллюзия.

Самыми первыми появились B-деревья с вполне приятными свойствами и удобное балансировкой. Их простейший подвид, наиболее удобный для работы в оперативной памяти – двоичное B-дерево, в вершинах которого либо указатель-значение-указатель, либо у-з-у-з-у (понятно как отсортированные). Логично что одновременно хочется и хранить все узлы одинаково, и не тратить два слова на нули: для этого можно хранить все узлы как у-з-у, а для больших вершин завести еще один фиктивный узел и повесить его в правый указатель настоящего.

Дополнительный бит появляется ровно тут, когда нужно научиться отличать расширение этого узла от настоящего указателя вниз.

Осталось два шага: во-первых, разрешить расширять узлы не только направо, но и налево, получая мега-узлы с тремя значениями и 4 указателями вниз; а во-вторых покрасить настоящие узлы в черный, а расширения в красный.

Книгу Сэджвика можно и не читать, но хотя бы его статью, где он первый (окей, как соавтор) придумывает красить 2-3-4 деревья в красные и черные цвета, стоило.

Если ты не троллишь, то смотри, логика тут очень простая.

Чтобы алгоритмы работали быстро, нужно чтобы дерево было сбаланированным

Чтобы поддерживать дерево сбалансированным и не при этом при его апдейте не сканировать его всего, нужно хранить доп. информацию в его узлах о балансировке этого поддерева (или его поддеревьев).

В случае красно-черного дерева этот бит, если он установлен, означает, что текущий узел вносит дисбаланс +1 в этом поддереве (корень поддерева – текущий узел).

Дальше просто требуем, чтобы два раза подряд дисбаланса не было.

В принципе можно ослаблять это требование и говорить, чтобы три раза или четыре раза подряд дисбаланса небыло, будет другая структура, но смысл тот же. Можно хранить не один бит, а два, и дать им смысл разницы в высоте поддеревьев, т.е. +1, -1, 0, тогда это будет AVL-дерево. Можно хранить больше битов, тогда можно делать деревья более сбаланированными, но алгоритмы усложняются.

В целом, кмк, всем оказалось удобнее использовать КЧ дерево, т.к. в нем есть баланс между сбалансированностью и скоростью/сложностью алгоритмов.