remove : 이진탐색트리(Binary Search Tree, BST)

이진탐색트리(Binary Search Tree, BST)에서 remove 메소드를 구현하는 것은 조금 더 복잡합니다. 노드를 제거할 때는 세 가지 주요 상황을 고려해야 합니다:

1. 리프 노드 제거: 제거하려는 노드가 리프 노드인 경우, 단순히 그 노드를 제거하면 됩니다.
2. 한 개의 자식을 가진 노드 제거: 제거하려는 노드가 하나의 자식만 가지고 있는 경우, 그 노드를 제거하고, 그 자식을 제거된 노드의 부모 노드에 연결합니다.
3. 두 개의 자식을 가진 노드 제거: 제거하려는 노드가 두 개의 자식을 가지고 있는 경우, 노드의 오른쪽 서브트리에서 가장 작은 값을 찾거나(또는 왼쪽 서브트리에서 가장 큰 값을 찾아) 그 값을 제거하려는 노드의 위치로 이동하고, 원래 그 값을 가지고 있던 노드를 제거합니다.

아래는 BST 클래스에 remove 메소드를 추가한 예시입니다. 이 예시는 노드를 제거하는 기본적인 로직을 구현합니다:

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}
 
class BST {
  constructor() {
    this.root = null;
  }
 
  // insert 메소드는 이전 예시와 동일하게 유지됩니다.
  // ...
 
  remove(data) {
    const removeNode = function(node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // 노드가 자식을 가지고 있지 않은 경우
        if (node.left == null && node.right == null) {
          return null;
        }
        // 노드가 하나의 자식만 가지고 있는 경우
        if (node.left == null) {
          return node.right;
        }
        if (node.right == null) {
          return node.left;
        }
        // 노드가 두 개의 자식을 가지고 있는 경우
        let tempNode = node.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    };
    this.root = removeNode(this.root, data);
  }
}
 

이 코드는 removeNode 함수를 재귀적으로 사용하여 트리에서 노드를 제거합니다. 제거 로직은 앞서 설명한 세 가지 경우를 처리합니다. 특히, 두 개의 자식을 가진 노드를 제거할 때는 오른쪽 서브트리에서 가장 작은 값을 찾아 그 값을 제거하려는 노드로 이동시키는 방법을 사용합니다. 그리고 나서, 원래 그 값을 가지고 있던 노드(이제는 빈 자리)를 재귀적으로 제거합니다.

remove 메소드의 구현은 이진탐색트리의 성질을 유지하면서 특정 노드를 안전하게 제거할 수 있게 해줍니다. 이 과정에서 트리의 구조가 변경될 수 있으므로, 트리의 균형을 유지하기 위한 추가 작업이 필요할 수 있습니다.