Java Reference
In-Depth Information
Using the method
getHeightDifference
, we can implement the previous pseudocode for
rebalance
within the class
AVLTree
as follows:
private
BinaryNodeInterface<T> rebalance(BinaryNodeInterface<T> nodeN)
{
int
heightDifference = getHeightDifference(nodeN);
if
(heightDifference > 1)
{
// left subtree is taller by more than 1,
// so addition was in left subtree
if
(getHeightDifference(nodeN.getLeftChild()) > 0)
// addition was in left subtree of left child
nodeN = rotateRight(nodeN);
else
// addition was in right subtree of left child
nodeN = rotateLeftRight(nodeN);
}
else if
(heightDifference < -1)
{
// right subtree is taller by more than 1,
// so addition was in right subtree
if
(getHeightDifference(nodeN.getRightChild()) < 0)
// addition was in right subtree of right child
nodeN = rotateLeft(nodeN);
else
// addition was in left subtree of right child
nodeN = rotateRightLeft(nodeN);
}
// end if
// else nodeN is balanced
return
nodeN;
}
// end rebalance
27.12
The method
add
.
Adding to an AVL tree is just like adding to a binary search tree, but with a rebal-
ancing step. For example, we can begin with the recursive implementations of the methods
add
and
addEntry
of
BinarySearchTree
(Segments 25.15 and 25.16 in Chapter 25) and insert calls to
rebalance
. The resulting methods in
AVLTree
are as follows:
public
T add(T newEntry)
{
T result =
null
;
if
(isEmpty())
setRootNode(
new
BinaryNode<T>(newEntry));
else
{
BinaryNodeInterface<T> rootNode = getRootNode();
result = addEntry(rootNode, newEntry);
setRootNode(rebalance(rootNode));
}
// end if
return
result;
}
// end add
private
T addEntry(BinaryNodeInterface<T> rootNode, T newEntry)
{
assert
rootNode !=
null
;
T result =
null
;
int
comparison = newEntry.compareTo(rootNode.getData());
