AVL Tree - зачем восстанавливать после вставки - PullRequest
Новая
       15

AVL Tree - зачем восстанавливать после вставки

0 голосов
/ 15 февраля 2019

Я смущен кодом для операции вставки в Wikipedia .Короче говоря, я не могу вспомнить пример того, что необходимо выполнить восстановление после вставки.Поскольку вставка всегда происходит в листовом узле, скажем, Z вставляется в узел X.Первое / самое раннее нарушение инварианта для дерева AVL (коэффициенты баланса должны быть в пределах [-1, 1]) может произойти только в parent(X).После того, как мы перебалансируем это небольшое поддерево, которое содержит только Z, X и parent(X), высота этого небольшого поддерева будет такой же, как и раньше, и не будет влиять на все остальные узлы.

Зачем нам нужен цикл до корня? 

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
// BalanceFactor(X) has to be updated:
if (Z == right_child(X)) { // The right subtree increases
    if (BalanceFactor(X) > 0) { // X is right-heavy
        // ===> the temporary BalanceFactor(X) == +2
        // ===> rebalancing is required.
        G = parent(X); // Save parent of X around rotations
        if (BalanceFactor(Z) < 0)      // Right Left Case     (see figure 5)
            N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
        else                           // Right Right Case    (see figure 4)
            N = rotate_Left(X, Z);     // Single rotation Left(X)
        // After rotation adapt parent link
    } else {
        if (BalanceFactor(X) < 0) {
            BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
            break; // Leave the loop
        }
        BalanceFactor(X) = +1;
        Z = X; // Height(Z) increases by 1
        continue;
    }
} else { // Z == left_child(X): the left subtree increases
    if (BalanceFactor(X) < 0) { // X is left-heavy
        // ===> the temporary BalanceFactor(X) == –2
        // ===> rebalancing is required.
        G = parent(X); // Save parent of X around rotations
        if (BalanceFactor(Z) > 0)      // Left Right Case
            N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
        else                           // Left Left Case
            N = rotate_Right(X, Z);    // Single rotation Right(X)
        // After rotation adapt parent link
    } else {
        if (BalanceFactor(X) > 0) {
            BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
            break; // Leave the loop
        }
        BalanceFactor(X) = –1;
        Z = X; // Height(Z) increases by 1
        continue;
    }
}
// After a rotation adapt parent link:
// N is the new root of the rotated subtree
// Height does not change: Height(N) == old Height(X)
parent(N) = G;
if (G != null) {
    if (X == left_child(G))
        left_child(G) = N;
    else
        right_child(G) = N;
    break;
} else {
    tree->root = N; // N is the new root of the total tree
    break;
}
// There is no fall thru, only break; or continue;
}

// Unless loop is left via break, the height of the total tree increases by 1.
...