Java Reference
In-Depth Information
S
X
X
S
C
A
B
B
C
A
(A)
(B)
Figure13.5 A single rotation in an AVL tree. This operation occurs when the
excess node (in subtree A) is in the left child of the left child of the unbalanced
node labeled S. By rearranging the nodes as shown, we preserve the BST property,
as well as re-balance the tree to preserve the AVL tree balance property. The case
where the excess node is in the right child of the right child of the unbalanced
node is handled in the same way.
S
X
Y
D
Y
X
S
A
C
A
C
B
B
D
(A)
(B)
Figure13.6 A double rotation in an AVL tree. This operation occurs when the
excess node (in subtree B) is in the right child of the left child of the unbalanced
node labeled S. By rearranging the nodes as shown, we preserve the BST property,
as well as re-balance the tree to preserve the AVL tree balance property. The case
where the excess node is in the left child of the right child of S is handled in the
same way.
4 can be fixed using a single rotation, as shown in Figure 13.5. Cases 2 and 3 can
be fixed using a double rotation, as shown in Figure 13.6.
The AVL tree insert algorithm begins with a normal BST insert. Then as the
recursion unwinds up the tree, we perform the appropriate rotation on any node
Search WWH ::




Custom Search