Java Reference
In-Depth Information
An implementation of this pseudocode follows:
// Corrects an imbalance at the node closest to a structural
// change in the left subtree of the node's right child.
// nodeN is a node, closest to the newly added leaf, at which
// an imbalance occurs and that has a right child.
private
BinaryNodeInterface<T> rotateRightLeft(BinaryNodeInterface<T> nodeN)
{
BinaryNodeInterface<T> nodeC = nodeN.getRightChild();
nodeN.setRightChild(rotateRight(nodeC));
return
rotateLeft(nodeN);
}
// end rotateRightLeft
The method
rotateLeftRight
has a similar implementation and is left as an exercise.
Question 11
Implement the algorithm given in Segment 27.3 for a single left rotation.
27.10
Rebalancing.
As you saw previously, you can correct an imbalance at node
N
of an AVL tree
caused by the addition of a node by performing only one of the following rotations, according to
where in the tree the change to its structure occurred:
•
Right rotation if the addition occurred in the left subtree of
N
's left child
•
Left-right rotation if the addition occurred in the right subtree of
N
's left child
•
Left rotation if the addition occurred in the right subtree of
N
's right child
•
Right-left rotation if the addition occurred in the left subtree of
N
's right child
The following pseudocode uses these criteria and the rotation methods to rebalance the tree:
Algorithm
rebalance(nodeN)
if
(nodeN
's left subtree is taller than its right subtree by more than 1
)
{
//
addition was in
nodeN
's left subtree
if
(
the left child of
nodeN
has a left subtree that is taller than its right subtree
)
rotateRight(nodeN)
//
addition was in left subtree of left child
else
rotateLeftRight(nodeN)
//
addition was in right subtree of left child
}
else if
(nodeN
's right subtree is taller than its left subtree by more than 1
)
{
//
addition was in
nodeN
's right subtree
if
(
the right child of
nodeN
has a right subtree that is taller than its left subtree
)
rotateLeft(nodeN)
//
addition was in right subtree of right child
else
rotateRightLeft(nodeN)
//
addition was in left subtree of right child
}
No rebalancing is needed if the heights of node
N
's two subtrees either are the same or differ by 1.
27.11
The method
rebalance
.
A method
getHeightDifference
that returns the difference in the heights
of a node's left and right subtrees would help us to implement the previous algorithm. By giving a
sign to the height difference it returns,
getHeightDifference
can indicate which subtree is taller.
This method can be defined within either the class
AVLTree
or the class
BinaryNode
. The latter
choice would be more efficient if each node maintained height information as one or more data
fields instead of recomputing it each time the method is called. (See Project 4.)
A node is unbalanced if its two subtrees differ in height by more than 1, that is, if
getHeightDifference
returns a value either greater than 1 or less than
-
1. If this return value is
greater than 1, the left subtree is taller; if it is less than
-
1, the right subtree is taller.
