Java Reference
In-Depth Information
179 updateHeight((AVLTreeNode<E>)A);
180 updateHeight((AVLTreeNode<E>)B);
181 updateHeight((AVLTreeNode<E>)C);
182 }
183
184 @Override /** Delete an element from the AVL tree.
185
update height
* Return true if the element is deleted successfully
186
* Return false if the element is not in the tree */
187
public boolean delete(E element) {
override delete
188
if (root == null )
189
return false ; // Element is not in the tree
190
191 // Locate the node to be deleted and also locate its parent node
192 TreeNode<E> parent = null ;
193 TreeNode<E> current = root;
194 while (current != null ) {
195 if (element.compareTo(current.element) < 0 ) {
196 parent = current;
197 current = current.left;
198 }
199 else if (element.compareTo(current.element) > 0 ) {
200 parent = current;
201 current = current.right;
202 }
203
else
204
break ; // Element is in the tree pointed by current
205 }
206
207
if (current == null )
208
return false; // Element is not in the tree
209
210 // Case 1: current has no left children (See FigureĀ 25.10)
211 if (current.left == null ) {
212 // Connect the parent with the right child of the current node
213 if (parent == null ) {
214 root = current.right;
215 }
216 else {
217 if (element.compareTo(parent.element) < 0 )
218 parent.left = current.right;
219 else
220 parent.right = current.right;
221
222 // Balance the tree if necessary
223 balancePath(parent.element);
224 }
225 }
226 else {
227 // Case 2: The current node has a left child
228 // Locate the rightmost node in the left subtree of
229 // the current node and also its parent
230 TreeNode<E> parentOfRightMost = current;
231 TreeNode<E> rightMost = current.left;
232
233 while (rightMost.right != null ) {
234 parentOfRightMost = rightMost;
235 rightMost = rightMost.right; // Keep going to the right
236 }
237
balance nodes
 
 
Search WWH ::




Custom Search