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