Черная глубина в красном Черное дерево? Как узнать, сбалансирован ли он?

Question

Во вторник у меня среднесрочный период, и у меня проблемы с пониманием красно-черных деревьев. Как я знаю, что дерево сбалансировано? Я знаю, что это как-то связано с правильным количеством черных узлов и глубиной черного. Но я не совсем понимаю это. Мне нужно это знать, потому что вы основываете повороты деревьев на этом. Если бы кто-то мог предоставить пошаговое объяснение, это было бы здорово. Спасибо!

Answer 1

Правила для красно-черного дерева:

• Корень черный
• Ноль узлы черные (иногда опущены)
• Красный узел не может иметь красного ребенка
• Путь от корня до каждого листа содержит одинаковое количество черных узлов

Итак, правило, на которое вы ссылаетесь - последнее, на что я полагаю. Другой способ выразить это, рисуя дерево: если вы представляете красно-черное дерево с черными ссылками, являющимися вертикальными, и красными ссылками, являющимися горизонтальными, то все листья оказываются на одном слое.

Если дерево следует этим четырем правилам, то оно является допустимым красно-черным деревом. Правило 1 и 2 легко исправить. Если дерево не следует правилу 3, это нарушение кода красного цвета, а если оно не следует правилу 4, это называется нарушением черного цвета.

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

        2,B                   2,B 

       /   \                 /   \ 

     1,B   0,R           1,B      6,B  

                        /        /   \   

                       0,B      4,R   8,R

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

В любом случае, отличное руководство по красно-черным деревьям можно найти здесь: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

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

Надеюсь это поможет.