BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 948

Daniel Daniel

Delete this
node

Adam Michael Michael

Jones To m Jones To m

Peter Peter

(a) Deleting Adam (b) After Adam is deleted

F IGURE 25.15

Deleting Adam falls into Case 1.

Daniel Daniel

Michael Jones

Delete this
node

Jones To m To m

Peter Peter

(a) Deleting Michael (b) After Michael is deleted

F IGURE 25.16

Deleting Michael falls into Case 2.

Note
It is obvious that the time complexity for the inorder, preorder, and postorder is O ( n ),
since each node is traversed only once. The time complexity for search, insertion, and
deletion is the height of the tree. In the worst case, the height of the tree is O ( n ). If a tree
is well-balanced, the height would be O (log n ). We will introduce well-balanced binary
trees in Chapter 26 and bonus Chapters 40 and 41.

BST time complexity

25.6

✓ ✓

Show the result of deleting 55 from the tree in Figure 25.4b.

Check

25.7

Point

Show the result of deleting 60 from the tree in Figure 25.4b.

25.8

What is the time complexity of deleting an element from a BST?

25.9

Is the algorithm correct if lines 204-208 in Listing 25.5 in Case 2 of the delete()
method are replaced by the following code?

parentOfRightMost.right = rightMost.left;