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