macOS rebalance_right function problem

[LtRammstein]

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.

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.

 

[Doctor Q]

That is some mighty odd code.

Compare the comment with the line below it:

// 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:

// 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.