Понимание факторов баланса / высоты узла для вращений AVL

Question

Поэтому мне трудно понять, как сбалансировать AVL-деревья. Я понимаю, что такое вращение, но я не могу понять, как найти коэффициент баланса высот узлов, например:

http://i.imgur.com/yh5zNIl.png

Может кто-нибудь объяснить мне, как мы на самом деле находим фактор баланса для каждого узла?

Я знаю, что если высота [(левое поддерево) - (правое поддерево)] не находится в пределах (-1<= x <= 1), то она не сбалансирована... но я не могу понять, как найти "x".

(редактировать: мне не нужен код, я просто хочу понять, как найти BF).

Answer 1

Коэффициент баланса узла - это разница высоты его левого и правого узлов-потомков.

Коэффициент баланса определяется некоторыми как: balance = node.left.height - node.right.height

и другими как: баланс = узел.райт.хайт - узел.лефт.хайт

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

Например, википедия определяет его как node.left.height - node.right.height, и вы можете видеть, что результаты формулы соответствуют коэффициентам баланса узлов Avl Tree Balance of Nodes Пример

Answer 2

X - высота левого поддерева - высота правого поддерева.

Если у левого поддерева максимальная высота равна трем, а у правого поддерева максимальная высота равна двум, тогда коэффициент баланса будет

3 - 2 = Balance Factor of 1 (Left Heavy)

Наоборот:

2 - 3 = Balance Factor of -1 (Right Heavy)

Если оба одинаковы:

3 - 3 = Balance Factor of 0 (Even Heavy)

Дерево становится несбалансированным, когда разница высот больше 1 или меньше -1.

5 - 3 = Balance Factor of 2 (UNBALANCED!)
3 - 5 = Balance Factor of -2 (UNBALANCED!)

Answer 3

Если я правильно понимаю ваш вопрос, вы хотите знать, как поддерживать баланс-фактор данного узла. Лучший способ сохранить трек - это сделать "вставку" в дерево. Это потому, что вы знаете, идет ли ваш новый узел слева или справа от "текущего" узла. Когда он идет влево, вы уменьшаете баланс, а когда он идет вправо, вы увеличиваете баланс. Идея состоит в том, чтобы дерево уже было сбалансировано до выхода из метода "insert".

Другой подход, который я видел, НЕ выполняет балансировку во время "вставки". Вы просто вставляете, как в BST. После вставки вы начинаете действие балансировки, где вы получаете левое поддерево и высоту правого поддерева в каждом узле и начинаете перетасовывать указатели. Это не очень хороший подход, так как вы берете O(logn) для каждого узла при поиске высоты, и поскольку вы делаете это для каждого узла, это приводит к n*O(logn).

Я публикую метод "вставки", который я когда-то написал, который поддерживает сбалансированное дерево при каждой вставке и НЕ вычисляет высоту отдельно в любой точке во время вставки. Посмотрите, поможет ли это:

Node*
AVL::insert(Node* node, int key, int value)
{
    if(node == NULL)
        node = new Node(key, value);

    else if (key <= node->key)
    {
        node->balance--;
        node->left = insert(node->left, key, value);
    }

    else if (key > node->key)
    {
        node->balance++;
        node->right = insert(node->right, key, value);  
    }

    // Right Tree Heavy
    if (node->balance == 2) 
    { 
        // Left tree unbalanced
        if (node->right && node->right->balance == 1) 
        {
            // LL
            node = singleLeftRotation(node);
            node->balance = 0;
            node->left->balance = 0;
        }
        if (node->right && node->right->balance == -1) 
        {
            // LR
            int nodeRLBalance = node->right->left->balance;
            node = doubleLeftRotation(node);
            node->balance = 0;
            node->left->balance = nodeRLBalance == 1 ? -1 : 0;
            node->right->balance = nodeRLBalance == -1 ? 1 : 0;
        }
    }

    // Left Tree Heavy
    if (node->balance == -2) 
    {
        // Right tree unbalanced
        if (node->left && node->left->balance == -1) 
        {
            // RR
            node = singleRightRotation(node);
            node->balance = 0;
            node->right->balance = 0;
        }
        if (node->left && node->left->balance == 1) 
        {
            // RL
            int nodeLRBalance = node->left->right->balance;
            node = doubleRightRotation(node);
            node->balance = 0;
            node->left->balance = nodeLRBalance == 1 ? -1 : 0;
            node->right->balance = nodeLRBalance == -1 ? 1 : 0;
        }
    }

    return node;
}

Answer 4

это изображение, вероятно, поможет вам. Несбалансированное дерево AVL имеет нарушение в E-узле

несбалансированное дерево AVL