Javascriptツリーのノードを削除する

ノードを遠くから見ると、ツリーからノードを削除するのは非常に複雑です。ノードを削除する際に考慮すべき3つのケースがあります。これらは、次の関数のコメントで言及されています。以前と同じように、クラス内にメソッドを作成し、再帰的に呼び出すヘルパーを作成します。

クラスメソッド

deleteNode(key) {
   // If a node is successfully removed, a reference will be received.
   return !(deleteNodeHelper(this.root, key) === false);
}

ヘルパーメソッド

/**
   * Takes root and key and recursively searches for the key.
   * If it finds the key, there could be 3 cases:
   *
   * 1. This node is a leaf node.
   *
   * Example: Removing F
   *     A
   *    / \
   *   B   C
   *  /   / \
   * D   E   F
   *
   * To remove it, we can simply remove its parent's connection to it.
   *
   *      A
   *     / \
   *    B   C
   *   /    /
   *  D    E
   *
   * 2. This node is in between the tree somewhere with one child.
   *
   * Example: Removing B
   *       A
   *      / \
   *     B   C
   *    /   / \
   *   D   E   F
   *
   * To remove it, we can simply make the child node replace the parent node in the above connection
   *       A
   *      / \
   *     D   C
   *        / \
   *       E   F
   *
   * 3. This node has both children. This is a tricky case.
   *
   * Example: Removing C
   *
   *        A
   *       / \
   *      B   C
   *     /   / \
   *    D   E   F
   *       /   / \
   *      G   H   I
   *
   * In this case, we need to find either a successor or a predecessor of the node and replace this node with
   * that. For example, If we go with the successor, its successor will be the element just greater than it,
   * ie, the min element in the right subtree. So after deletion, the tree would look like:
   *
   *        A
   *       / \
   *      B   H
   *     /   / \
   *    D   E   F
   *       /     \
   *      G       I
   *
   * To remove this element, we need to find the parent of the successor, break their link, make successor's left
   * and right point to current node's left and right. The easier way is to just replace the data from node to be
   * deleted with successor and delete the sucessor.
*/
function deleteNodeHelper(root, key) {
   if (root === null) {
      // Empty tree return false;
   }
   if (key < root.data) {
      root.left = deleteNodeHelper(root.left, key);
      return root;
   } else if (key > root.data) {
      root.right = deleteNodeHelper(root.right, key);
      return root;
   } else {
      // No children
      //case 1 - a leaf node
      if (root.left === null && root.right === null) {
         root = null;
         return root;
      }
      // Single Child cases
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;

      // Both children, so need to find successor
      let currNode = root.right;
      while (currNode.left !== null) {
         currNode = currNode.left;
      }
      root.data = currNode.data;
      // Delete the value from right subtree.
      root.right = deleteNodeHelper(root.right, currNode.data);
      return root;
   }
}

これは、-

例

let BST = new BinarySearchTree();

BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
 
BST.inOrder();

BST.deleteNode(15);
BST.deleteNode(10);
BST.deleteNode(3);

BST.inOrder();

出力

これにより、出力が得られます-

5
7
12
50