Блог

Насколько я понимаю, бинарные деревья не обязательно должны быть полными. Однако кажется, что RBT должны быть заполнены (иногда дочерние элементы равны нулю). Это правда, или я что-то упускаю?

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

Общая идея красно-черного алгоритма заключается в ограничении фактической максимальной разницы в общей высоте конечных узлов (а не только высоты черного) между конечным узлом с кратчайшим общим путем и конечным узлом с самым длинным общим путем. Если вы используете это в качестве основы, то дерево RB является «полным», если все конечные узлы имеют одинаковую общую высоту (так же, как обычное двоичное дерево заполнено, если все листья имеют одинаковую глубину), и дерево RB не нужно заполнять.

Нет. Красно-черные деревья не всегда заполнены. На самом деле это редкое событие. Вы можете узнать больше об этом, прочитав книгу «Введение в алгоритмы» (Cormen, стр. 308), 3-е издание (в нем есть несколько рисунков, иллюстрирующих ответ на стр. 310, я не показываю их из-за авторских прав).