문제 상황
다음은 이진 탐색 트리(Binary Search Tree) 자료구조를 생성하고 노드를 삽입하는 기능을 제공하는 코드입니다.
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
// 이진 탐색 트리의 루트
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 루트 노드를, 두 번째 인수로 숫자 값을 받습니다.
두 번째 인수로 지정한 값이 트리에 존재하면 해당 값을 가진 노드를 삭제하고, 존재하지 않으면 아무 작업도 수행하지 않습니다. 두 경우 모두 함수는 갱신된 BST의 루트를 반환해야 합니다.
구현 예제
이를 구현한 전체 코드는 다음과 같습니다.
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
// 이진 탐색 트리의 루트
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 Node();
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('노드 삭제 전');
printTree(BST.root);
console.log('데이터가 4인 노드 삭제 후');
printTree(deleteNode(BST.root, 4));코드 설명
삭제할 대상 노드를 찾은 뒤에는 세 가지 경우를 고려해야 합니다.
리프 노드: 왼쪽 자식도 오른쪽 자식도 없는 경우
자식이 하나인 경우: 왼쪽만 있거나 오른쪽만 있는 경우
자식이 둘인 경우: 왼쪽과 오른쪽 자식이 모두 있는 경우
첫 번째와 두 번째 경우는 비교적 간단합니다. null을 반환하거나 남아 있는 자식(왼쪽 또는 오른쪽)을 그대로 반환하면 됩니다.
마지막 경우가 가장 까다롭습니다. 대상 노드를 삭제한 후 그 자리를 무엇으로 대체할지 결정해야 하는데, 단순히 왼쪽이나 오른쪽 자식을 위로 끌어올리면 BST의 정렬 규칙이 깨져 유효하지 않은 트리가 됩니다. 따라서 오른쪽 서브트리에서 가장 작은 값(중위 후속자) 또는 왼쪽 서브트리에서 가장 큰 값(중위 선행자)을 찾아 대체해야 합니다.
위 코드에서는 오른쪽 서브트리의 최솟값을 찾는 방식을 사용했습니다. while 루프를 통해 오른쪽 서브트리의 가장 왼쪽 노드까지 내려간 뒤, 그 값을 새 노드에 복사하고 원래 위치에 있던 노드를 재귀적으로 삭제합니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
노드 삭제 전
2
3
4
5
6
7
데이터가 4인 노드 삭제 후
2
3
5
6
7