об операции вставки дерева AVL

После вставки невозможно, чтобы левый и правый потомки поддерева оставались одинаковыми при изменении высоты.

Давайте рассмотрим простой пример только с ‹3 узлами в поддереве. Возможные факторы баланса:

• +1 - это корневой узел в поддереве с 1 левым дочерним элементом и без правого дочернего элемента.
• -1 - это корневой узел в поддереве с 1 правым дочерним элементом и без левого дочернего элемента.
• 0 - Корневой узел в поддереве имеет по 1 узлу справа и слева.

Для поддерева с коэффициентом баланса +1,

• если мы вставляем в право, мы в порядке
• если мы вставляем в левый, коэффициент баланса изменится на 2. Поэтому нам нужно сбалансировать дерево, и в этом случае высота поддерева изменится.

Для поддерева с коэффициентом баланса -1,

• если мы вставляем в левый, мы в порядке
• если мы вставляем в правую, коэффициент баланса изменится на -2. Поэтому нам нужно сбалансировать дерево, и в этом случае высота поддерева изменится.

Для поддерева с коэффициентом баланса 0,

• если мы вставляем в левый, мы в порядке. Высота изменена, но также изменен и дочерний узел.
• если мы вставляем в право, мы в порядке. Высота изменена, но также изменен и дочерний узел.

Таким образом, невозможно изменить высоту и по-прежнему иметь одинаковую высоту правого и левого дочерних элементов.

На странице двоичного дерева Википедии:

Сбалансированное бинарное дерево имеет минимально возможную максимальную высоту (также известную как глубина) для листовых узлов, потому что для любого заданного количества листовых узлов листовые узлы размещаются на максимально возможной высоте.

Одной из распространенных сбалансированных древовидных структур является бинарная древовидная структура, в которой левое и правое поддеревья каждого узла отличаются по высоте не более чем на 1.

Например:

Это сбалансированное дерево.

И если мы вставим 1, его высота увеличится на 1. Тем не менее, это снова сбалансированное дерево. Потому что левое и правое поддеревья отличаются по высоте не более чем на 1.

Кстати, дерево AVL — это самобалансирующееся бинарное дерево поиска. Так что невозможно потерять равновесие после вставки. Потому что после каждой вставки дерево балансирует себя, совершая необходимые повороты.

Мне кажется, вы неправильно используете термин сбалансированный. Вы считаете сбалансированным отсутствие разницы в росте, но это не более 1 разницы в высоте в определении.

Ваш вопрос:

В стандартном процессе вставки дерева AVL возможно ли увеличение высоты поддерева на единицу (из-за операции вставки и поворота), в то время как поддерево (после увеличения высоты на единицу) по-прежнему имеет ту же высоту слева/ правильный ребенок?

Если бы у нас было дерево, имеющее одинаковую высоту с левой и правой ветвей, и если бы мы вставили узел в листовой узел на левой ветви, высота увеличилась бы, потому что высота дерева равна maximum(height(left_branch, right_branch)). Потому что после этой операции height(left_branch) равно height(right_branch)+1. Значит, они не могут быть равны.

Короче говоря, ваше предварительное условие height(left_branch) == height(right_branch)

Ваша операция increasing height of left_branch by 1

Таким образом, условие height(left_branch) == height(right_branch) больше не может быть правдой.