문제
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