Обновление коэффициента баланса в дереве AVL после поворота - что я делаю не так?

Question

Я работаю над реализацией дерева AVL в c ++ и знаком с концепциями одинарного и двойного вращения. Я успешно реализовал дерево, рассчитав balance_factor = height(left_child) - height(right_child) и , пытаясь реализовать более эффективное дерево AVL, сохранив его коэффициент баланса и сохранив его в диапазоне [-1, 1] . Обратите внимание, что в настоящее время я смотрю только на вставку, прежде чем пытаться удалить основанные вне баланса коэффициенты.

По сути, псевдокод для вставки выглядит следующим образом:

1. Найти правильныйместо для вставки узла, помещая каждый узел, к которому осуществляется доступ, в стек, начиная с корневого узла
2. Обновлять коэффициенты баланса всех узлов в стеке по одному, но останавливаясь, если коэффициент баланса установлен на 0 вprocess.
3. Используя стек, рекурсивно сбалансируйте дерево в любом узле, который содержит balance_factor из -2 или 2.

Пока что кажется, что этот алгоритм более илиless работает с некоторыми наборами значений, , но не работает в некоторых ситуациях.

Вставка значений от 0 до 9 случайным образом (коэффициенты баланса верны)

Случайная вставка строковых значений (неверный коэффициент баланса корневых узлов после поворота LR

При просмотре дерева строк AVL мой алгоритм прекращает распространение, как только он достигаетузел, у которого значение balance_factor обновлено до 0. В нижнем случае обновление коэффициентов баланса останавливается на one[0], а коэффициент баланса корневого узла fad[-1] не обновляется до 0, хотя его поддеревья делят то же самоемаксимальная высота.

На вики-странице деревьев AVL указано, что:

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

Однако я не могу понять, почему это так, когда ротация LR / RL потенциально требует распространения обновления значений balance_factor за пределы такого узла.

TL; DR: я делаю что-то концептуально неправильно?

Вставка

template <typename T>
void AVLTree<T>::insert(const T& value)
{
    std::stack<BinTree> path_nodes;
    insert_in_node(BSTree<T>::get_root(), value, path_nodes);
}

template <typename T>
void AVLTree<T>::insert_in_node(BinTree& node, const T& value,
    std::stack<BinTree>& path_nodes)
{
    if (!node)
    {
        node = BSTree<T>::make_node(value);
        update_balance_factors(path_nodes, value, true);
        balance(path_nodes);
    }
    else
    {
        ++node->count;
        path_nodes.push(node);

        if (value < node->data)
            insert_in_node(node->left, value, path_nodes);
        else if (value > node->data)
            insert_in_node(node->right, value, path_nodes);
    }
}

Балансировка / Обновление значений коэффициента баланса

template <typename T>
void AVLTree<T>::balance(std::stack<BinTree>& path_nodes)
{
    while (!path_nodes.empty())
    {
        BinTree tree = path_nodes.top();
        path_nodes.pop();

        int balanceFactor = tree->balance_factor;

        if (balanceFactor < -1 || balanceFactor > 1)
        {
            // there is a need to rotate and balance
            if (balanceFactor > 0)
            {
                // left side is deeper than right side
                if (tree->left->balance_factor > 0)
                {
                    // LL
                    rotate_right(tree);
                }
                else
                {
                    // LR
                    rotate_left(tree->left);
                    rotate_right(tree);
                }
            }
            else
            {
                // right side is deeper than left side
                if (tree->right->balance_factor < 0)
                {
                    // RR
                    rotate_left(tree);
                }
                else
                {
                    // RL
                    rotate_right(tree->right);
                    rotate_left(tree);
                }
            }

            reparent(path_nodes, tree);
            update_balance_factors(path_nodes, tree->data, false);
        }
    }
}

template <typename T>
void AVLTree<T>::update_balance_factors(std::stack<BinTree> path_nodes,
    const T& value, bool inserting)
{
    while (!path_nodes.empty())
    {
        BinTree parent = path_nodes.top();
        path_nodes.pop();

        if (value < parent->data)
        {
            // value belongs to the left subtree
            if (inserting)
                ++parent->balance_factor;
            else
                --parent->balance_factor;
        }
        else
        {
            // value belongs to the right subtree
            if (inserting)
                --parent->balance_factor;
            else
                ++parent->balance_factor;
        }

        // break out of loop if balance factor is adjusted to 0
        if (!parent->balance_factor)
            break;
    }
}

Поворот / Воспроизведение

template <typename T>
void AVLTree<T>::rotate_left(BinTree& pivot)
{
    BinTree temp = pivot;
    pivot = pivot->right;
    temp->right = pivot->left;
    pivot->left = temp;

    temp->count -= ((pivot->right) ? pivot->right->count : 0) + 1;
    pivot->count += ((temp->left) ? temp->left->count : 0) + 1;

    temp->balance_factor += 1
        - ((pivot->balance_factor < 0) ? pivot->balance_factor : 0);

    pivot->balance_factor += 1
        + ((0 < temp->balance_factor) ? temp->balance_factor : 0);
}

template <typename T>
void AVLTree<T>::rotate_right(BinTree& pivot)
{
    BinTree temp = pivot;
    pivot = pivot->left;
    temp->left = pivot->right;
    pivot->right = temp;

    temp->count -= ((pivot->left) ? pivot->left->count : 0) + 1;
    pivot->count += ((temp->right) ? temp->right->count : 0) + 1;

    temp->balance_factor -= 1
        + ((pivot->balance_factor > 0) ? pivot->balance_factor : 0);

    pivot->balance_factor -= 1
        - ((0 > temp->balance_factor) ? temp->balance_factor : 0);
}

template <typename T>
void AVLTree<T>::reparent(std::stack<BinTree>& path_nodes,
    const BinTree& orphan)
{
    if (path_nodes.empty())
    {
        BSTree<T>::get_root() = orphan;
    }
    else
    {
        BinTree parent = path_nodes.top();
        if (parent->data < orphan->data)
            parent->right = orphan;
        else
            parent->left = orphan;
    }
}

Любая помощь будет принята с благодарностью!