Если узел вставлен в дерево AVL, может случиться так, что один из узлов на пути к new_node потеряет баланс высоты. Но мой вопрос: если этот узел зафиксирован, могут ли другие узлы над ним (от предков до корня) по-прежнему сохранять дисбаланс высоты (в случае, если они потеряли баланс ранее).
Я сделал некоторые документы и заметил, что такой сценарий невозможен. Как только дисбаланс высоты фиксируется в узле, все его предки должны быть исправлены автоматически (если они были затронуты).





Дисбаланс можно исправить локально; Всего необходимо рассмотреть четыре случая. Точнее, это два случая (одинарное вращение и двойное вращение), причем два других являются их зеркальными версиями; операции описаны здесь. Нет необходимости следовать по пути к корню и повторно балансировать каждый узел на этом пути. В целом, перебалансировку можно выполнить за постоянное время.