PDA

View Full Version : rebalance_right function problem




LtRammstein
Dec 7, 2006, 05:43 PM
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
Dec 7, 2006, 07:13 PM
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.