rebalance_right function problem

Discussion in 'Mac Programming' started by LtRammstein, Dec 7, 2006.

  1. macrumors 6502a

    LtRammstein

    Joined:
    Jun 20, 2006
    Location:
    Denver, CO
    #1
    Okay, I'm implementing a rebalance_right function from some source code I got from a text book, and for some reason, either it's because I'm not thinking or what, but I'm very confused on how to do it since right nodes are never symmetric.

    If you can give me some insight on how to do this, I'd be very appreciative.

    Code:
    template<typename Item_Type>
    void AVL_Tree<Item_Type>::rebalance_right(BTNode<Item_Type>*& local_root) {
      // Cast local_root to an AVLNode pointer
      AVLNode<Item_Type>* AVL_local_root =
        dynamic_cast<AVLNode<Item_Type>*>(local_root);
      // Obtain reference to the left child
      AVLNode<Item_Type>* right_child = 
        dynamic_cast<AVLNode<Item_Type>*>(local_root->right);
      // See whether left-right-heavy
      if (right_child->balance == AVLNode<Item_Type>::LEFT_HEAVY) {
        // Obtain a reference to the left-right child
        AVLNode<Item_Type>* right_left_child = 
          dynamic_cast<AVLNode<Item_Type>*>(right_child->right);
        // Adjust the balances to be the new values after rotations are 
        // performed
        if (right_left_child->balance == AVLNode<Item_Type>::LEFT_HEAVY) {
          right_child->balance = AVLNode<Item_Type>::BALANCED;
          right_right_child->balance = AVLNode<Item_Type>::RIGHT_HEAVY;
          AVL_local_root->balance = AVLNode<Item_Type>::BALANCED;
        } else if (right_left_child->balance 
                   == AVLNode<Item_Type>::BALANCED) {
          right_child->balance = AVLNode<Item_Type>::BALANCED;
          right_left_child->balance = AVLNode<Item_Type>::LEFT_HEAVY;
          AVL_local_root->balance = AVLNode<Item_Type>::BALANCED;
        } else {
          right_child->balance = AVLNode<Item_Type>::LEFT_HEAVY;
          right_left_child->balance = AVLNode<Item_Type>::BALANCED;
          AVL_local_root->balance = AVLNode<Item_Type>::BALANCED;
        }
        // Perform left rotation
        rotate_right(local_root->right);
      } else { // Left-Left case
        /* In this case the left child (the new root) and the
           local root (new right child) will both be balanced
           after the rotation.
        */
        right_child->balance = AVLNode<Item_Type>::BALANCED;
        AVL_local_root->balance = AVLNode<Item_Type>::BALANCED;
      }
      // Finally rotate right
      rotate_left(local_root);
    }
    
    Don't mind the comments, they are kinda worthless since I've changed the code a little, I left it in there so I can change it back fairly quickly.
     
  2. Administrator

    Doctor Q

    Staff Member

    Joined:
    Sep 19, 2002
    Location:
    Kepler-452b
    #2
    That is some mighty odd code.

    Compare the comment with the line below it:
    Code:
    // Obtain reference to the left child
    AVLNode<Item_Type>* right_child = dynamic_cast<AVLNode<Item_Type>*>(local_root->right);
    It gets the right child, not the left child.

    Another oddity:
    Code:
    // Obtain a reference to the left-right child
    AVLNode<Item_Type>* right_left_child = dynamic_cast<AVLNode<Item_Type>*>(right_child->right);
    The comment calls it left-right but the variable is named right_left, while the code gets the right child of the right child! How are you supposed to know what they have in mind?

    Is this supposed to be a working example, one that is deliberately mistaken, or something else? I guess I don't have enough context for what you want to do with this code.
     

Share This Page