Создание узла
Процедура добавления нового узла требует определения правого ключа родительского узла и уровня иерархии. Алгоритм включает обновление существующих ключей в дереве и вставку нового узла.
Основные этапы:
- Обновление ключей узлов, расположенных после родительского.
- Обновление родительской ветки.
- Сдвиг последующих узлов.
- Вставка нового узла с соответствующими параметрами.
Удаление узла
Удаление узла требует учёта возможных подчинённых элементов. Процесс использует левый и правый ключи удаляемого узла.
Этапы удаления:
- Удаление узла и всей его ветки.
- Обновление ключей родительской ветки с вычислением длины диапазона.
- Обновление последующих узлов с уменьшением значений.
Перемещение узла
Наиболее сложная операция. Узел может перемещаться в две основные области: вышестоящих и нижестоящих узлов.
Перемещение вверх по дереву предусматривает определение областей для левого и правого ключей с последующим изменением значений в одном оптимизированном запросе.
Перемещение вниз по дереву использует отличающиеся условия выбора диапазонов и включает вычисление смещения ключей редактируемого узла через формулу:
[right_key_near] − [left_key] + 1 − [skew_tree]