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

Question

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

Каково максимальное количество вращений при вставке нового элемента в n-элемент красное черное дерево?

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

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

1

red-black-tree tree-rotation

Источник

user2095534 10 фев '14 в 18:37

1 ответ

Решение

Другие вопросы по тегам red-black-tree tree-rotation

user1737817 21 мар '14 в 12:55 2014-03-21 12:55 · Accepted Answer · 2014-03-21 12:55

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

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

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