JavaScrip의 이진 검색 트리에서 원하는 노드 삭제

문제

Binary Search Tree 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의 루트를 첫 번째 인수로, 숫자 값을 두 번째 인수로 취하는 또 다른 함수 deleteNode()를 작성해야 합니다.

그리고 두 번째 인수에 의해 지정된 값이 트리에 존재하면 함수는 값을 보유하는 노드를 삭제해야 합니다. 그렇지 않으면 함수는 아무 작업도 수행하지 않습니다. 두 경우 모두 우리 함수는 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));

코드 설명:

대상 노드를 찾았을 때 생각해야 하는 조건은 총 세 가지입니다.

• 잎(왼쪽 없음, 오른쪽 없음);

• 왼쪽, 오른쪽 없음; 왼쪽이 없고 오른쪽이 있습니다.

• 왼쪽과 오른쪽이 있습니다.

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