Может ли существовать любое действительное красно-черное дерево?

Ответ 1

Я считаю, что вставка узлов в обход ширины (уровень) приведет к красно-черному дереву.

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

Поскольку вы вставляете их в порядке уровня, у вас не может быть дерева, которое менее сбалансировано, чем исходное дерево. Никаких исключений не требуется, и при вставке не требуется никаких поворотов. В вашем примере вы должны вставить их в следующем порядке:

13,8,17,1,11,15,25,6,22,27

Изменить. Хотя это приведет к созданию двоичного дерева поиска с правильными значениями и формой, это может не сгенерировать правильные цвета... это зависит от реализации функции вставки. Причина в определении красно-черных деревьев позволяет варьировать цвета узлов, когда дерево имеет более одного узла и заполнено, а все листья находятся на одной глубине - после определения Википедии это "идеальное" двоичное дерево:

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Предположим, что дерево имеет три узла со значениями {1,2,3}, где "2" является корнем и по определению является черным. Узлы {1,3} могут быть либо черными, либо обоими красными, не нарушая красно-черных правил. Таким образом, вполне допустимая реализация красно-черной вставки может обнаружить, когда дерево "идеально" и цвет каждого узла черный. Такая реализация предотвратит возможность создания дерева, которое, например, чередуется с черным и красным на каждом уровне.

Изменить 2: Учитывая, что оба красно-чёрных дерева являются возможными входами (все три узла черные, а узлы 1 и 3 красные), это решает вопрос о необходимости удаления, если есть решение, тогда необходимо удаление. Теперь вопрос в моем сознании заключается в том, существует ли только один способ реализации вставки/удаления красно-черного дерева. Если их несколько, и если они дают разные деревья, то игроку игры нужно будет понять реализацию, чтобы указать порядок вставки и удаления для построения данного красно-черного дерева. Я не знаю достаточно о реализации красно-черных деревьев, чтобы ответить на вопрос, существует ли только один способ их реализации или существует ли более одного.

Ответ 2

Я думаю, что отрасль математики, которая занимается этим типом проблемы, представляет собой теорию графов, и изучая некоторые документы теории графов, которые проверяют свойства красного черного и других сбалансированных деревьев, я приведу к этой статье: http://www.math.unipd.it/~ baldan/Papers/Soft-copy-pdf/cosmicah05.pdf и http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf и этот документ http ://citeseerx.ist.psu.edu/viewdoc/download? doi = 10.1.1.87.1161 & rep = rep1 & type = pdf, они должны иметь возможность отвечать на ваши запросы на абстрактные свойства. Или, по крайней мере, помогите вам рассказать свой вопрос таким образом, который приведет к еще большему количеству ресурсов.

Ответ 3

если дерево соответствует следующим правилам:

• Узел либо красный, либо черный.
• Корень черный.
• Все листья (NIL) черные.
• Оба ребенка каждого красного узла черные.
• Каждый простой путь от данного узла к любому из его потомков оставляет одно и то же количество черных узлов.

Это будет сбалансированное двоичное дерево и может называться красно-черным деревом.

Вставка и удаление дерева красно-черных имеют особые условия и правила. Если дерево, как в вашем примере, следует алгоритму вставки и удаления дерева RB, оно всегда будет деревом RB. Во время вставки и удаления небалансное двоичное дерево всегда будет восстанавливаться до сбалансированного дерева, изменяя цвет узла, Вращающийся узел или ветвь.

Ответ 4

Я думаю, что то, о чем вы просите здесь, является официальным доказательством того, может ли любое произвольное, законное красно-черное дерево быть построено серией вставок и исключений, если дерево будет перебалансировано после каждой операции. Я не собираюсь делать такого доказательства, но я думаю, что у меня есть идея, как вы могли бы построить такое доказательство.

Я бы исчерпывающе рассмотрел все возможные под деревья с участием всех законных перестановок вокруг одного узла и доказал, что он может быть построен. Так:

• черный узел
  • нет родителя
    • левый ребенок null
      • правый ребенок null
      • правый ребенок не равен нулю
    • левый ребенок не равен нулю
      • правый ребенок null
      • правый ребенок не равен нулю
  • это левый ребенок
    • как указано выше
  • является правильным ребенком
    • как указано выше
• красный узел (не может иметь родителя)
  • это левый ребенок
    • как указано выше
  • является правильным ребенком
    • как указано выше

И тогда вам нужно создать индуктивный шаг, показывающий, что любое произвольное дерево является перестановкой случаев, показанных выше. Кажется довольно прямолинейным, когда я так выразился, но, как я уже упоминал в своем комментарии, я слишком ржавый, чтобы справиться с фактическим доказательством.