Процедура балансировки дерева AVL - PullRequest
Новая
       51

Процедура балансировки дерева AVL

0 голосов
/ 03 ноября 2018

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

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

private Node balance(Node x) {
    if (Math.abs(height(x.left) - height(x.right)) <= 1) {
        return x;
    }
    // left sub tree is heavier than right sub tree
    if (height(x.left) > height(x.right)) {
        // right sub tree of left sub tree is heavier than left sub tree of left sub tree
        if (height(x.left.left) < height(x.left.right)) {
            leftRotate(x.left);
        }
        return rightRotate(x);
    }
    // right sub tree is heavier than left sub tree
    else {
        // left sub tree of right sub tree is heavier than right sub tree of right sub tree
        if (height(x.right.left) > height(x.right.right)) {
            rightRotate(x.right);
        }
        return leftRotate(x);
    }
}

Когда я смотрел на решения MIT (стр. 5) , кажется, что они выполняют вращение влево и затем вращение вправо, если узел вставлен в левое поддерево левого поддерева несбалансированного узла:

enter image description here

Согласно моему пониманию, если мы вставим узел в левое поддерево левого поддерева неуравновешенного узла, нам следует только вращение вправо, а не вращение влево и последующее вращение вправо.

Что мне здесь не хватает? Правильно ли я это реализовал?

1 Ответ

0 голосов
/ 03 ноября 2018

Вы действительно нашли ошибку в документе , на который есть ссылка на стр. 5.

Изображения на странице 4 правильные, но реализация на странице 5 неправильная, вероятно, опечатка.

Логически линии 4-7 должны отражать линии 8-11 с точки зрения левой и правой. Имея это в виду, очевидно, что там есть ошибка.

Строка 5 должна иметь влево и вправо подкачки - или же использовать < вместо >, что сводится к тому же самому - вот так:

5 если высота ( слева [ y ]) <<em> высота ( справа [ y ])

В этом отношении ваша реализация верна.

...