AVL TREES - Introduction to Java Programming: Comprehensive Version - page 975

121 }
122
123 A.left = C.right; // Make T3 the left subtree of A
124 B.right = C.left; // Make T2 the right subtree of B
125 C.left = B;
126 C.right = A;
127
128 // Adjust heights
129 updateHeight((AVLTreeNode<E>)A);
130 updateHeight((AVLTreeNode<E>)B);
131 updateHeight((AVLTreeNode<E>)C);
132 }
133
134 /** Balance RR (see Figure 26.3) */
135 private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) {
136 TreeNode<E> B = A.right; // A is right-heavy and B is right-heavy
137
138 if (A == root) {
139 root = B;
140 }
141 else {
142 if (parentOfA.left == A) {
143 parentOfA.left = B;
144 }
145 else {
146 parentOfA.right = B;
147 }
148 }
149
150 A.right = B.left; // Make T2 the right subtree of A
151 B.left = A;
152 updateHeight((AVLTreeNode<E>)A);
153 updateHeight((AVLTreeNode<E>)B);
154 }
155
156 /** Balance RL (see Figure 26.5) */
157 private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) {
158 TreeNode<E> B = A.right; // A is right-heavy
159 TreeNode<E> C = B.left; // B is left-heavy
160
161 if (A == root) {
162 root = C;
163 }
164 else {
165 if (parentOfA.left == A) {
166 parentOfA.left = C;
167 }
168 else {
169 parentOfA.right = C;
170 }
171 }
172
173 A.right = C.left; // Make T2 the right subtree of A
174 B.left = C.right; // Make T3 the left subtree of B
175 C.left = A;
176 C.right = B;
177
178

update height

RR rotation

update height

RL rotation

// Adjust heights