JavaScripのバイナリ検索ツリーから目的のノードを削除する

問題

バイナリ検索ツリーDSを作成し、ノードを挿入する機能を提供する次のコードがあるとします-

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);

このコードを実行すると、BSTは次のようになります-

5
/ \
3 6
/ \ \
2 4 7

最初の引数として任意のBSTのルートを取り、2番目の引数として数値を受け取るさらに別の関数deleteNode（）を作成する必要があります。

また、2番目の引数で指定された値がツリーに存在する場合、関数は値を保持するノードを削除する必要があります。それ以外の場合、関数は何も実行しません。どちらの場合も、関数はBSTの更新されたルートを返す必要があります。

例

このためのコードは-

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);
const printTree = (node) => {
   if(node !== null) {
      printTree(node.left);
      console.log(node.data);
      printTree(node.right);
   };
};
const deleteNode = function(root, key) {
   if(!root){
      return null;
   };
   if(root.data > key){
      if(!root.left){
         return root;
      }else{
         root.left = deleteNode(root.left, key);
      };
   } else if(root.data < key){
      if(!root.right) return root;
      else root.right = deleteNode(root.right, key);
   } else {
      if(!root.left || !root.right){
         return root.left || root.right;
      } else {
         let nd = new TreeNode();
         let right = root.right;
         nd.left = root.left;
         while(right.left){
            right = right.left;
         }
         nd.data = right.data;
         nd.right = deleteNode(root.right, right.data);
         return nd;
      }
   }
   return root;
};
console.log('Before Deleting any node');
printTree(BST.root);
console.log('After deleting node with data 4');
printTree(deleteNode(BST.root, 4));

コードの説明：

ターゲットノードを見つけたら、合計3つの条件を考慮する必要があります。

• 葉（左なし、右なし）;

• 去った、右ではない。左はありません、右があります;

• 左と右の両方があります。

1と2は簡単です。nullまたは私たちが持っているもの（左または右）を返す必要があります。

そして最後の条件として、ターゲットノードを削除した後、何がそれを置き換えるのかを知る必要があります。単に左または右にドラッグすると、BSTは無効になります。したがって、右側のサブツリーから最小のものを見つけるか、左側のサブツリーから最大のものを見つける必要があります。

出力

そして、コンソールの出力は-

Before Deleting any node
2
3
4
5
6
7
After deleting node with data 4
2
3
5
6
7