To delete an element from a BST, first locate it in the tree and then consider two cases—whether or not the node has a left child—before deleting the element and reconnecting the tree. The insert(element) method was presented in the post. Often you need to delete an element from a binary search tree. Doing so is far more complex than adding an element into a binary search tree.
To delete an element from a binary search tree, you need to first locate the node that contains the element and also its parent node. Let current point to the node that contains the element in the binary search tree and parent point to the parent of the current node. The current node may be a left child or a right child of the parent node. There are two cases to consider.
Case 1: The current node does not have a left child, as shown in Figure below (a). In this case, simply connect the parent with the right child of the current node, as shown in Figure below (b).
For example, to delete node 10 in Figure below (a), you would connect the parent of node 10 with the right child of node 10, as shown in Figure below (b).
If the current node is a leaf, it falls into Case 1. For example, to delete element 16 in Figure above (a), connect its right child (in this case, it is null) to the parent of node 16.
Case 2: The current node has a left child. Let rightMost point to the node that contains the largest element in the left subtree of the current node and parentOfRightMost point to the parent node of the rightMost node, as shown in Figure below (a). Note that the rightMost node cannot have a right child but may have a left child. Replace the element value in the current node with the one in the rightMost node, connect the parentOfRightMost node with the left child of the rightMost node, and delete the rightMost node, as shown in Figure below (b).
For example, consider deleting node 20 in Figure below (a). The rightMost node has the element value 16. Replace the element value 20 with 16 in the current node and make node 10 the parent for node 14, as shown in Figure below (b).
The algorithm for deleting an element from a binary search tree can be described in the code below.
1 boolean delete(E e) {
2 Locate element e in the tree;
3 if element e is not found
4 return true;
5
6 Let current be the node that contains e and parent be
7 the parent of current;
8
9 if (current has no left child) // Case 1
10 Connect the right child of
11 current with parent; now current is not referenced, so
12 it is eliminated;
13 else // Case 2
14 Locate the rightmost node in the left subtree of current.
15 Copy the element value in the rightmost node to current.
16 Connect the parent of the rightmost node to the left child
17 of rightmost node;
18
19 return true; // Element deleted
20 }
The complete implementation of the delete method is given in lines 153–211 in BST.java. The method locates the node (named current) to be deleted and also locates its parent (named parent) in lines 155–168. If current is null, the element is not in the tree. Therefore, the method returns false (line 171). Please note that if current is root, parent is null. If the tree is empty, both current and parent are null.
Case 1 of the algorithm is covered in lines 174–185. In this case, the current node has no left child (i.e., current.left == null). If parent is null, assign current.right to root (lines 176–178). Otherwise, assign current.right to either parent.left or parent.right, depending on whether current is a left or right child of parent (180–183).
Case 2 of the algorithm is covered in lines 186–207. In this case, current has a left child. The algorithm locates the rightmost node (named rightMost) in the left subtree of the current node and also its parent (named parentOfRightMost) (lines 193–196). Replace the element in current by the element in rightMost (line 199); assign rightMost.left to either parentOfRightMost.right or parentOfRightMost.left (lines 202–206), depending on whether rightMost is a right or left child of parentOfRightMost.
The code below gives a test program that deletes the elements from the binary search tree.
Inorder (sorted): Adam Daniel George Jones Michael Peter Tom
Postorder: Daniel Adam Jones Peter Tom Michael George
Preorder: George Adam Daniel Michael Jones Tom Peter
The number of nodes is 7
After delete George:
Inorder (sorted): Adam Daniel Jones Michael Peter Tom
Postorder: Adam Jones Peter Tom Michael Daniel
Preorder: Daniel Adam Michael Jones Tom Peter
The number of nodes is 6
After delete Adam:
Inorder (sorted): Daniel Jones Michael Peter Tom
Postorder: Jones Peter Tom Michael Daniel
Preorder: Daniel Michael Jones Tom Peter
The number of nodes is 5
After delete Michael:
Inorder (sorted): Daniel Jones Peter Tom
Postorder: Peter Tom Jones Daniel
Preorder: Daniel Jones Tom Peter
The number of nodes is 4
Figures below show how the tree evolves as the elements are deleted from it.
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(logn).
Top comments (0)