Как сбалансировать висячий узел в дереве AVL - PullRequest
Новая
       8

Как сбалансировать висячий узел в дереве AVL

0 голосов
/ 16 мая 2018

У меня есть последовательность чисел, которые должны быть помещены в дерево AVL:

50, 22, 80, 70, 75, 73

Я не уверен, куда 73 идет. В моем понимании первый баланс происходит, когда 75 становится правильным ребенком 70: 

  50
 /  \
22   80
    /
  70
    \
    75

Таким образом, 80 - это «несбалансированный» узел, а 70 - тяжелый левый ребенок. Итак, 70 движется влево и 80 движется вправо, как-то так: 

      50
     /  \
    22   75
        /  \
       70   80

При добавлении 73 мы снова становимся неуравновешенными: 

      50
     /  \
    22   75
        /  \
       70   80
         \
          73

Как мне сбалансировать это? Я не могу просто поставить 73 между 75 и 70, не так ли?

1 Ответ

0 голосов
/ 20 мая 2018

Существует четко определенная процедура для восстановления баланса дерева AVL.

  1. Начните с недавно вставленного узла и двигайтесь к корню, пока не найдете несбалансированный узел.
  2. Как только вы окажетесь на несбалансированном узле, определите, является ли он тяжелым слева или справа тяжелым.
  3. Если он справа тяжелый, а его правые потомки тоже справа тяжелый, то вам придется выполнить один левый поворот.
  4. Если его правое тяжелое тело и его правые дочерние элементы оставлены тяжелыми (это соответствует вашему случаю), то вам придется выполнить двойное вращение справа налево.

для левого тяжелого случая есть симметричная процедура, которую, я полагаю, вы сможете выяснить самостоятельно.

псевдокод для вышеуказанной процедуры будет выглядеть примерно так. 

     z=firstUnbalancedNode();
     if(rightHeavy(z))
     {
          if(rightHeavy(z.rightChild))
          {
               rotateLeft(z.rightChild);
          }
          else
          {
               rotateRight(z.rightChild)
               rotateLeft(z.rightChild)
          }
      }

в вашем случае

  1. мы вставляем 73 и движемся вверх, чтобы найти несбалансированный узел (если есть).
  2. мы находим 50, который неуравновешен.
  3. 50 тяжелый справа, а его правые дочерние элементы (75) тяжелые слева, что означает, что нам придется выполнять вращение вправо-влево.

после вставки дерево выглядит так 

      50
     /  \
    22   75
        /  \
       70   80
         \
          73

теперь мы выполняем вращение вправо на правого 50-го ребенка (75). после этого дерево вращения выглядит так 

      50
     /  \
    22  70
          \
           75
          /  \
         73   80

после этого мы должны выполнить левый поворот 50-го правого ребенка (70). который преобразует дерево в следующую структуру. 

        70
       /  \
      50   75
     /    /  \
    22   73   80

так что, как вы можете видеть, есть два основных поворота. Лево и право. в некоторых случаях эту работу можно выполнить одним вращением, а в некоторых других случаях вам может потребоваться выполнить оба поворота.

...