Сценарий вставки дерева RB
Я смотрел на рис. 5 примеров вставок в этом уроке красно-черного дерева:
Я думаю, что даже до вставки нового узла с ключом xдерево уже нарушает правило, которое гласит:
Все внешние узлы черного цвета должны быть одинаковыми.
На мой взгляд, высота черных внешних узлов в узле 15 на 1 больше, чем черная высота внешних узлов в узле 8,
Я обнаружил, что этот вариант использования описан во всех учебниках и онлайн-ресурсах, поэтому я запутался здесь.
Как дерево было на самом деле деревом RB до вставки нового узла?