Максимум. количество поворотов при вставке нового элемента в n-элементное красно-черное дерево

Каково максимальное количество поворотов при вставке нового элемента в n-element Red Black Tree?

Если я прав, вставка, не нарушающая правила RBT, требует максимум 2 вращений (2 случая). Если это так, O(1) тоже правильный ответ?

Если это так, подтвердите и скажите, пожалуйста, для чего требуется максимум 3 поворота?


red-black-tree tree-rotation
person Kamil Gosciminski    schedule 10.02.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

При правильной реализации красно-черного дерева требуется максимум 3 операции (или 2 поворота). Например, центральному BST, показанному на этом изображении, потребуется 3 операции, чтобы он соответствовал правилам Red Black BST.

Изображение для демонстрации случая, когда необходимы 3 операции

Изображение взято из слайдов Роберта Седжвика из этого MOOC..

person Nikunj Banka    schedule 21.03.2014