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