Как определить нарушенный узел в дереве AVL?
Я кодирую функцию вставки AVL. Скажите, пожалуйста, как я могу определить узел, баланс которого нарушается при вставке нового узла? Я знаю, как рассчитать коэффициент баланса любого узла. Но если я добавлю узел в виде листа, как я могу узнать об узле-предке, чей баланс нарушен? так что я могу применить вращение к нему. Спасибо в ожидании.
Решение
Как только вы добавляете лист, вы переходите к родителям один за другим к корню и обновляете их высоту (или глубину, если хотите). Когда вы обновляете высоту деревьев, вы проверяете, не вышли ли они из баланса, и перебалансируете их. Затем вы продолжаете двигаться вверх снова.
Это O(log(n)) операция, поскольку путь от любого листа до корня в дереве AVL содержит O(log(n)) узлы и ребалансировка узла делается в O(1)
Другие решения
Как только вы получите коэффициент баланса (в моем случае (высота левого поддерева — высота правого поддерева)),
- Если коэффициент баланса больше 1, то текущий узел не сбалансирован, и мы находимся либо в левом левом случае, либо в левом правом случае. Чтобы проверить, является ли он левым регистром или нет, сравните вновь вставленный ключ с ключом в левом корне поддерева.
- Если коэффициент баланса меньше -1, то текущий узел
несбалансирован, и мы находимся либо в правой правой стороне, либо в правой левой стороне.
Чтобы проверить, правильно ли это дело или нет, сравните недавно
вставлен ключ с ключом в правом поддереве корня.
Отвечает ли это на ваш вопрос?
detector