การลบโหนดที่ต้องการจาก Binary Search Tree ใน 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

เราจำเป็นต้องเขียนฟังก์ชันอื่น deleteNode() ที่รับรูทของ BST ใดๆ เป็นอาร์กิวเมนต์แรกและค่าตัวเลขเป็นอาร์กิวเมนต์ที่สอง

และถ้าค่าที่ระบุโดยอาร์กิวเมนต์ที่สองมีอยู่ใน Tree ฟังก์ชันของเราควรลบโหนดนั้นที่เก็บค่าไว้ มิฉะนั้น ฟังก์ชันของเราจะไม่ทำอะไรเลย ในทั้งสองกรณี ฟังก์ชันของเราควรส่งคืนรูทที่อัปเดตของ 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