Мне интересно, есть ли фундаментальная проблема для перебалансировки дерева AVL. Согласно нескольким руководствам, для вставки AVL можно сбалансировать максимум 2 поворота. Однако это может зависеть от того, что называется сбалансированным. Перейдите по ссылке, чтобы увидеть дерево.
Изначально в нем 6 элементов. Предположим, что мы вставили последнее значение как 3, 4,5, 5,5 или 6,5. В любом случае он будет вставлен слева внизу. В качестве всего 7-элементного дерева для идеальной балансировки я буду считать, что оно имеет только 3 ряда.
Это приведет к тому, что новый корень будет 6 или 6.5 (если мы вставим 6.5). Я действительно не могу придумать способ перебалансировать его за 2 оборота. Если мы будем полагаться только на определение «баланса», 4 строки по-прежнему будут называться сбалансированными, но это приведет к увеличению времени поиска.
Я что-то упускаю?
В случае, если изображение было удалено, ниже представлена текстовая версия:
7
5 9
4 6 8 Empty_slot
3 or 4.5 or 5.5 or 6.5
