insert_rebalance в красно-черном дереве

Вставка_перебалансировки в rb_tree в основном нуждается в двух поворотах?

Я так не думаю!

введите здесь описание изображения

«1» — самый новый узел вставки. Это случай 1: текущий узел красный, отец красный, дядя красный.

Таким образом, мы устанавливаем цвет отца как черный, цвет дяди как черный, цвет отца отца как красный, и устанавливаем отца отца как текущий узел, и продолжаем идти.

После вышеперечисленных операций это снова случай 1.

Представим: если всегда будет случай 1, то числа поворота будут не просто 2, а может и больше.

Мои приведенные выше утверждения верны? Я хочу подтвердить свою мысль.


algorithm tree red-black-tree
person Limer    schedule 30.08.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если место вставки является случайным, то два поворота довольно необычны.

Начиная с 0 узлов:

B (0% нужно два оборота)

b r (25% требуется два оборота)

b r r (0% нужно два оборота)

b b b r (20% требуется два оборота)

b b b r r (0% требуется два оборота)

На шагах, где возможны два поворота, также можно заполнить дерево, не требуя второго поворота. Если расположение вставки всегда максимальное, а не случайное, то количество вставок с двумя поворотами равно 0, но вы будете вращаться один раз примерно в 50% случаев.

person SoronelHaetir    schedule 11.01.2018