การลบ Node ใน Tree ด้วย JavaScript

การลบ Node จาก tree ค่อนข้างซับซ้อนถ้าดูจากระยะไกล มี 3 กรณีที่ต้องพิจารณาเมื่อลบ node ซึ่งอธิบายใน comment ของฟังก์ชันต่อไปนี้ เหมือนเดิมเราจะสร้าง method ในคลาสและ helper สำหรับ recursive call

Class method

deleteNode(key) {
  // ถ้าลบ node สำเร็จ จะได้ reference กลับมา
  return !(deleteNodeHelper(this.root, key) === false);
}

Helper method

function deleteNodeHelper(root, key) {
  if (root === null) {
    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 {
    // ไม่มี children - case 1: 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;
    // มีทั้งสอง children ต้องหา successor
    let currNode = root.right;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    root.data = currNode.data;
    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