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