AVL tree perfect balancing issue

Question

Мне интересно, есть ли фундаментальная проблема для повторного балансировки дерева AVL. Согласно нескольким учебным пособиям, для вставки AVL, максимум 2 вращается, он может быть сбалансирован. Однако это может зависеть от того, что называется сбалансированным. Следуйте за link, чтобы увидеть дерево.

Первоначально он имеет 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 

Answer 1

Как вы можете прочитать на wikipedia

В дереве AVL, высоты два дети поддерев любого узел отличается не более чем одним

Это не означает, что у вас есть полное дерево! См. Примеры дерева балансов на странице wikipedia.

Таким образом, для любого из вставки вы предлагаете вам дерево по-прежнему будет сбалансирован (для общего определения сбалансирован) после вставки

на одной стороне корня вы будете иметь поддерево

 5 
    4  6  height 2 
3 # # # 

и на стороне Одер вы бы поддерево

9 
8 #    height 1 

Как thoses 2 поддеревьев только разница высоты 1, так что это нормально ... и вы можете CHEC k, что это свойство верно для всех узлов