Я хочу доказать утверждение в заголовке, но мне нужна помощь.Моя отправная точка состоит в том, что узел дерева AVL хранит коэффициент баланса, а не высоту поддерева, имеющего его в качестве корневого: это должно предотвратить переход вверх, изменяя поле height
Часть вставки проста,Если мы вставим новый узел в дерево AVL, первым потенциально несбалансированным предком будет прародитель.Поскольку вращение корня поддерева не меняет высоту самого поддерева, после того, как мы выполнили одно-два поворота, необходимые для восстановления баланса прародителя , нам не нужно перебалансировать других предков .
Удаление является причиной затруднений.Я убежден, что требовалось фиксированное количество вращений, потому что я никогда не находил дерево AVL, требующее O (log (n)) вращений для удаления узла.Это, однако, не доказывает, что такого дерева AVL не существует.
Мы игнорируем случай, когда у узла есть два дочерних элемента: узел, который мы будем истинно удалять, будет его преемником или предшественником,у обоих из них только один или ноль дочерних элементов.
Мы игнорируем случай дерева, полученного ранее проанализированными деревьями путем замены левого и правого дочерних узлов: это не меняет саму структуру дерева.
Давайте предположим, что мы удаляем узел и вынуждены вращать его родителя и / или его дедушку.Вращение корня не изменяет высоту его поддерева: так же, как и в операции вставки, после одного-двух поворотов корень поддерева дедушки должен иметь нулевой коэффициент баланса и его высоту без изменений до удаления,Таким образом, никакой предок не нуждается в перебалансировке.
Как сделать это «доказательство» менее неопределенным, не создавая все деревья AVL и проверяя одну за другой?