Java Reference
In-Depth Information
63
if
(balanceFactor((AVLTreeNode<E>)A.right) >=
0
) {
64 balanceRR(A, parentOfA);
// Perform RR rotation
65 }
66
else
{
67 balanceRL(A, parentOfA);
// Perform RL rotation
68 }
69 }
70 }
71 }
72
73
/** Return the balance factor of the node */
74
private int
balanceFactor(AVLTreeNode<E> node) {
75
if
(node.right ==
null
)
// node has no right subtree
76
return
-node.height;
77
else if
(node.left ==
null
)
// node has no left subtree
78
return
+node.height;
79
else
80
return
((AVLTreeNode<E>)node.right).height -
81 ((AVLTreeNode<E>)node.left).height;
82 }
83
84
/** Balance LL (see FigureĀ 26.2) */
85
private void
balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) {
86 TreeNode<E> B = A.left;
// A is left-heavy and B is left-heavy
87
88
if
(A == root) {
89 root = B;
90 }
91
else
{
92
if
(parentOfA.left == A) {
93 parentOfA.left = B;
94 }
95
else
{
96 parentOfA.right = B;
97 }
98 }
99
100 A.left = B.right;
// Make T2 the left subtree of A
101 B.right = A;
// Make A the left child of B
102 updateHeight((AVLTreeNode<E>)A);
103 updateHeight((AVLTreeNode<E>)B);
104 }
105
106
/** Balance LR (see FigureĀ 26.4) */
107
private void
balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) {
108 TreeNode<E> B = A.left;
// A is left-heavy
109 TreeNode<E> C = B.right;
// B is right-heavy
110
111
if
(A == root) {
112 root = C;
113 }
114
else
{
115
if
(parentOfA.left == A) {
116 parentOfA.left = C;
117 }
118
else
{
119 parentOfA.right = C;
120 }
RR rotation
RL rotation
get balance factor
LL rotation
update height
LR rotation
Search WWH ::
Custom Search