Vấn đề
Giả sử, chúng ta có đoạn mã sau tạo DS Cây tìm kiếm nhị phân và cung cấp chức năng chèn nút -
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); Sau khi thực thi chính đoạn mã này, BST của chúng ta sẽ trông giống như thế này -
5 / \ 3 6 / \ \ 2 4 7
Chúng tôi được yêu cầu viết thêm một hàm deleteNode () lấy trong gốc của bất kỳ BST nào làm đối số đầu tiên và một giá trị số làm đối số thứ hai.
Và nếu giá trị được chỉ định bởi đối số thứ hai tồn tại trong Cây, hàm của chúng ta sẽ xóa nút đó giữ giá trị, nếu không hàm của chúng ta sẽ không làm gì cả. Trong cả hai trường hợp, hàm của chúng tôi sẽ trả về gốc được cập nhật của BST.
Ví dụ
Mã cho điều này sẽ là -
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)); Giải thích mã:
Có tổng cộng ba điều kiện mà chúng ta cần nghĩ đến khi chúng ta tìm thấy nút đích.
-
một chiếc lá (không trái, không phải);
-
có trái, không phải; không có trái, có phải;
-
có cả bên trái và bên phải.
1 và 2 rất dễ dàng, chúng ta chỉ cần trả về null hoặc bất cứ thứ gì chúng ta có (trái hoặc phải);
Và đối với điều kiện cuối cùng, chúng ta cần biết rằng sau khi chúng ta xóa nút đích, điều gì sẽ thay thế nó. Nếu chúng ta chỉ cần kéo nó sang trái hoặc phải lên, BST sẽ không xuất hiện. Vì vậy, chúng ta phải tìm nhỏ nhất từ cây con bên phải hoặc lớn nhất từ cây con bên trái.
Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7