자바스크립트 이진 탐색 트리에서 노드 삭제하기

트리(Tree)에서 노드를 제거하는 작업은 언뜻 보기에 상당히 복잡해 보일 수 있습니다. 노드를 삭제할 때는 노드의 구조에 따라 세 가지 경우를 고려해야 합니다. 이 글에서는 각 경우를 차례대로 살펴본 뒤, 지금까지의 패턴처럼 클래스 메서드와 재귀 호출용 헬퍼(helper) 함수로 나누어 구현하겠습니다.

노드 삭제의 3가지 경우

경우 1: 리프 노드(자식 없음)

삭제하려는 노드가 자식이 없는 리프 노드라면, 부모 노드와의 연결만 끊어주면 간단히 제거할 수 있습니다. 아래 예시에서 F를 제거해 보겠습니다.

      A
     / \
    B   C
   /   / \
  D   E   F

F를 제거하면 부모 C와의 연결만 끊어주면 됩니다.

      A
     / \
    B   C
   /   /
  D   E

경우 2: 자식이 하나인 노드

노드가 트리 중간에 있지만 자식이 하나뿐이라면, 해당 자식 노드가 부모의 자리를 대체하도록 연결만 변경하면 됩니다. 아래 예시에서 B를 제거해 보겠습니다.

        A
       / \
      B   C
     /   / \
    D   E   F

B의 자식 D가 B의 위치를 대체합니다.

        A
       / \
      D   C
         / \
        E   F

경우 3: 자식이 둘인 노드

자식이 둘 다 있는 경우가 가장 까다롭습니다. 이때는 삭제할 노드의 후계자(successor) 또는 전임자(predecessor)를 찾아 그 값으로 대체한 뒤, 후계자를 삭제하는 방식으로 처리합니다. 여기서는 후계자를 사용하겠습니다. 후계자란 현재 값보다 큰 원소 중 가장 작은 값, 즉 오른쪽 서브트리에서 최솟값을 의미합니다.

아래 예시에서 C를 제거한다고 해보겠습니다.

        A
       / \
      B   C
     /   / \
    D   E   F
       /   / \
      G   H   I

C의 오른쪽 서브트리(E, F, G, H, I)에서 최솟값은 H입니다. 따라서 C의 값을 H로 교체한 뒤, 오른쪽 서브트리에서 H를 삭제하면 다음과 같은 트리가 됩니다.

        A
       / \
      B   H
     /   / \
    D   E   F
       /     \
      G       I

정리하면, 후계자의 부모를 찾아 연결을 끊고 후계자의 좌우 자식을 현재 노드의 좌우 자식에 연결하는 것이 원리입니다. 실제 구현에서는 더 간단하게 삭제할 노드의 데이터를 후계자의 데이터로 교체한 뒤, 후계자를 재귀적으로 삭제하는 방식을 사용합니다.

구현

클래스 메서드

노드가 성공적으로 제거되면 헬퍼 함수가 유효한 참조를 반환하므로, 이를 확인하여 true 또는 false를 반환합니다.

deleteNode(key) {
  // 노드가 성공적으로 제거되면 참조가 반환됩니다.
  return !(deleteNodeHelper(this.root, key) === false);
}

헬퍼 메서드

루트와 키를 받아 재귀적으로 키를 검색하고, 키를 찾으면 위에서 살펴본 3가지 경우에 맞게 처리합니다.

/**
 * 루트(root)와 키(key)를 받아 해당 키를 재귀적으로 검색합니다.
 * 키를 찾으면 다음 3가지 경우 중 하나에 해당합니다.
 *
 * 1. 리프 노드인 경우 → 부모와의 연결을 끊고 null 반환
 * 2. 자식이 하나인 경우 → 유일한 자식이 현재 노드의 자리를 대체
 * 3. 자식이 둘인 경우 → 오른쪽 서브트리의 최솟값(후계자)으로 값 교체 후,
 *    오른쪽 서브트리에서 후계자를 재귀적으로 삭제
 */
function deleteNodeHelper(root, key) {
  if (root === null) {
    // 트리가 비어 있으면 false 반환
    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 {
    // 자식이 없는 경우 (case 1 - 리프 노드)
    if (root.left === null && root.right === null) {
      root = null;
      return root;
    }
    // 자식이 하나인 경우
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;

    // 자식이 둘 다 있으므로 후계자(오른쪽 서브트리의 최솟값)를 찾음
    let currNode = root.right;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    root.data = currNode.data;
    // 오른쪽 서브트리에서 후계자 값을 삭제
    root.right = deleteNodeHelper(root.right, currNode.data);
    return root;
  }
}

참고로 노드 삭제 연산의 시간 복잡도는 트리의 높이에 비례합니다. 균형 잡힌 BST에서는 평균적으로 O(log n), 최악의 경우(편향된 트리)에는 O(n)이 소요됩니다.

실행 예제

다음과 같이 테스트할 수 있습니다. 먼저 7개의 값을 삽입한 뒤 중위 순회(in-order)로 출력하고, 15, 10, 3을 차례로 삭제한 후 다시 중위 순회를 수행합니다.

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이며, 중위 순회는 항상 오름차순으로 값을 출력하므로 아래와 같은 결과를 얻습니다.

출력 결과

5
7
12
50