C++ дерево AVL баланс

Я столкнулся с проблемой балансной части моего дерева. У меня вызывается checkBal после рекурсивной вставки. Если я попытаюсь добавить 5, 2 и 4, он проверит баланс 2 и продолжит обратно до 5, а затем перейдет в правильную часть rotateLeft правого поворота. Но ошибка функции rotateLeft во второй строке.

Что не так с этой реализацией? Я искал повсюду и сравнивал то, что я делал, с тем, как люди говорят о том, как это делается. У меня наконец все заработало. Я забыл установить N на K в конце.

//==============================================================================
//===== Set Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
    // Make sure to check the children are balanced as well.
    if (locRoot->left != NULL)
        locRoot->left = checkBal(locRoot->left);
    if (locRoot->right != NULL)
        locRoot->right = checkBal(locRoot->right);

    if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
    {
        if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
            locRoot->left = rotateRight(locRoot->left);
        locRoot = rotateLeft(locRoot);
    }
    else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
    {
        if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
            locRoot->right = rotateLeft(locRoot->right);
        locRoot = rotateRight(locRoot);
    }
    updateHeights(locRoot);
    return locRoot;
}
    /*
        Extream cases of balancing a tree requires a double rotation
            A
             \
              D
             /
            B

        'A' is the current root
        If right->left (grandchild) is larger then the right->right (grandchild)
        First Right rotate the child then left rotate the parent


        left > right by 2 or more
            left.left < left.right  (Double Right Rotation)
            left.left >= left.right (Single Right Rotation)
        right > left by 2 or more
            right.right < right.left (Double Left Rotation)
            right.right >= right.left (Single Left Rotation)
    */

sNode<T>* rotateRight(sNode<T> *N) const
{
/*
      N           K
     / \         / \
   (a)  K  =>   N  (c)
       / \     / \
     (b) (c) (a) (b)
*/
    // K is going to be our new Parent
    // Move (c) from K->right to N->left
    // Set K->right to be N
    // Return the new parent node to update the one above.
    sNode<T> *K = N->right;
    N->right = K->left;        
    K->left = N;
    return N = K;
}

c++ avl-tree tree-balancing
person LF4    schedule 05.06.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward 

rotateRight(locRoot->left);

должно быть,

rotateRight(locRoot->right);

но это все еще неправильная реализация. =p

У вас должны быть разные реализации для левой и правой сторон корня.
Попробуйте посмотреть анимация из Википедии.

person guiltry    schedule 05.06.2012
comment
Что вы имеете в виду, что у меня должна быть другая реализация для левой и правой сторон корня? Двойное право просто означает поворот левого дочернего элемента влево, а затем родительского вправо. Спасибо, я не заметил эту копию/опечатку, хотя это не должно было вызываться в моем тестовом примере. - person LF4; 05.06.2012
comment
Я не знаю, что вы имеете в виду под «двойным правом» просто означает поворот левого дочернего элемента влево, а затем родительского вправо. Случай справа-справа (посмотрите на изображение из Википедии), 4 will be poited by a *root, 3 will be pointed by a *t, затем t->right = root->left root->left = t готово. - person guiltry; 05.06.2012

arrow_upward
0
arrow_downward

Я заработал после того, как немного повозился с ним. Мое решение ниже.

//==============================================================================
//===== AVL Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
    // Go all the way down to the leaf nodes.
    if (locRoot->left != NULL)
        locRoot->left = checkBal(locRoot->left);
    if (locRoot->right != NULL)
        locRoot->right = checkBal(locRoot->right);

    // Before we do anything lets update the parent/child heights
    updateHeights(locRoot);

    if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
    {
        // If it needs a double left rotate first rotate the left child right
        if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
            locRoot->left = rotateRight(locRoot->left);
        locRoot = rotateLeft(locRoot);
    }
    else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
    {
        // If it needs a double right rotate first rotate the right child left
        if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
            locRoot->right = rotateLeft(locRoot->right);
        locRoot = rotateRight(locRoot);
    }
    // Update the new heights
    updateHeights(locRoot);
    return locRoot;
}
    /*
        Extream cases of balancing a tree requires a double rotation
            A
             \
              D
             /
            B

        'A' is the current root
        If right->left (grandchild) is larger then the right->right (grandchild)
        First Right rotate the child then left rotate the parent


        left > right by 2 or more
            left.left < left.right  (Double Right Rotation)
            left.left >= left.right (Single Right Rotation)
        right > left by 2 or more
            right.right < right.left (Double Left Rotation)
            right.right >= right.left (Single Left Rotation)
    */

sNode<T>* rotateRight(sNode<T> *N) const
{
/*
      N           K
     / \         / \
   (a)  K  =>   N  (c)
       / \     / \
     (b) (c) (a) (b)
*/
    // K is going to be our new Parent
    // Move (c) from K->right to N->left
    // Set K->right to be N
    // Return the new parent node to update the one above.
    sNode<T> *K = N->right;
    N->right = K->left;        
    K->left = N;
    return N = K;
}

sNode<T>* rotateLeft(sNode<T> *N) const
{
/*
         N            K
    / \          / \
       K  (a)  =>  (b)  N
      / \              / \
    (b) (c)          (c) (a)
*/
    sNode<T> *K = N->left;
    N->left = K->right;        
    K->right = N;
    return N = K;
}
person LF4    schedule 20.06.2012