Binary tree “study notes” – delete operation

This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Delete a child node of a binary tree

This is a little bit more complicated, so you have to deal with it case by case. First, find the node to delete, if not found, do not delete; The handling method is as follows:

First, define some temporary variables, and compare the searched key with the key value of the current node. If the key value is smaller, search for the left subtree, if the key value is larger, search for the right subtree, and then find the node to be deleted through the loop.

 var current = this.root;
 var parent = null;
 var isLeftChild = true
 while(current.key ! = key) { parent = current;if (key < current.key) {
         isLeftChild = true;
         current = current.left;
     } else {
         isLeftChild = false;
         current = current.right;
     }
     if (current == null) return false;
 }
Copy the code

There are three situations after finding:

Delete the leaf node

Check if the left and right of the current node are null and are not the root node. If it’s the root, then it’s like emptying the binary tree.

if (current.left == null && current.right == null) {
    if (current == this.root) {
        this.root = null;
    } else if (isLeftChild) {
        parent.left = null;
    } else {
        parent.right = null; }}Copy the code

Delete a node that has only one child node

There are two ways to think about this, the child node may be a left child node or a right child node; But the idea is the same in both cases, so it’s good to deal with them separately; If the node you want to delete has a left child node, the same is true for the right.

1. Check whether the node is the root node

   In either case, remember to first determine if the node you want to delete is the root node; Because if it is the root node, it is not handled the same way as other node locations. If it is the root node, set the child node to the root node again.

2. Determine whether the node to be deleted is to the left or right of its parent node

   If the current node is the left child of its parent, then the children of the current node will be connected to the left child of its parent. Same thing on the right-hand side.

if (current.right == null) {
    if (current == this.root) {
        this.root = current.left;
    } else if (isLeftChild) {
        parent.left = current.left;
    } else {
        parent.right = current.left
    }
}
Copy the code

Delete a node that has two child nodes

This case is the most complicated…. In each case, we need to replace the current node with a child node closest to the current node. So what would be the closest?

That’s the maximum value in the left subtree of current, and the minimum value in the right subtree of current, which means you’re going to go to the far right of the left subtree of current until this node points to null, or you’re going to go to the far left of the right subtree of current until this node points to null; This node is the one that can replace the current node.

For example, in the graph below, if you want to remove the 15 node, you can replace it with 14 or 18.

Precursor & successor: A node slightly smaller than current is called the precursor of the current node; A node slightly larger than current is called the successor of the current node. In other words, if we delete current, we need to find its predecessor or successor;

The following is an example of finding a successor:

1. The first step is to find a successor

   Loop to find its successor. This successor may be a son of current, or it may be several generations away. If it is several generations away, the replacement node should point to the right subtree of the original current node.

   Also, if the successor node has children, the parent of the successor node points to the children of the successor node; For example, in the figure above, when you replace 20 with 18, you not only want 18 to point to the subtree of 20, but also 20 to point to the child node 19 of 18;

   var successor = delNode;
   var current = delNode.right;
   var successorParent = delNode;
   while(current ! =null) {
       successorParent = successor;
       successor = current;
       current = current.left
   }
   // 3. Check whether the desired successor node is the right node of delNode
   if(successor ! = delNode.right) { successorParent.left = successor.right; successor.right = delNode.right }return successor;
   Copy the code

2. Give the parent and left subtree of the original current to the successor node

   The first thing to do is to determine whether or not this node is the root node, and if so let the root node point directly to this successor node; If not then say whether current is in the left subtree or the right subtree at that point and let the parent of current point to the succeeded; And let the left subtree of current be assigned to the succeeded

   if (current == this.root) {
       this.root = successor;
   } else if (isLeftChild) {
       parent.left = successor;
   } else {
       parent.right = successor;
   }
   successor.left = current.left;
   Copy the code