JavaScript 이진 탐색 트리 구현: 중복 키와 세 가지 삭제 처리

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

순서 정보를 저장하면 어떤 일이 쉬워지는가

일반 이진 트리는 왼쪽과 오른쪽의 값 관계를 보장하지 않아 특정 값을 찾으려면 모든 노드를 볼 수 있습니다. BST는 각 노드의 왼쪽 부분 트리에 더 작은 키, 오른쪽 부분 트리에 더 큰 키만 두어 한쪽을 제외합니다. 단순 존재 확인뿐 아니라 정렬 순회와 범위 검색이 필요한 상황에 의미가 있습니다.

정렬 배열은 이진 탐색이 빠르지만 중간 삽입·삭제에 이동이 필요합니다. 해시 테이블은 정확한 키 조회에 적합하지만 순서에 따른 범위 열거를 직접 지원하지 않습니다. BST는 연결을 바꿔 갱신하면서 순서를 유지하는 선택이며, 이 글의 비균형 BST는 높이까지 보장하지 않는다는 대가가 있습니다.

키·중복·반환값 계약

키는 JavaScript 안전 정수만 허용합니다. NaN은 작다·크다 비교가 모두 false이므로 검사 없이 넣으면 다른 키를 같은 키처럼 처리할 위험이 있습니다. 실수나 문자열 정렬이 필요하다면 모든 메서드에서 일관된 비교 규칙을 별도로 설계해야 합니다.

같은 키는 새 노드로 만들지 않고 count를 증가시킵니다. 따라서 부분 트리 간 비교는 엄격한 부등호이고 각 키는 노드 하나에만 존재합니다. delete는 해당 키 한 개만 지워 성공 여부를 반환합니다. count가 2라면 첫 삭제 후 노드는 남고 두 번째 삭제에서 연결 구조를 바꿉니다.

root와 노드는 설명을 위해 노출하지만 외부에서 key·count·연결을 바꾸지 않는 계약입니다. insert는 인스턴스를 반환하고 has는 불리언, inorder와 range는 중복 횟수만큼 키를 담은 새 배열을 반환합니다. 범위는 양 끝을 포함하며 low > high면 빈 배열입니다.

전체 코드와 실행

아래를 bst.cjs로 저장하고 Node.js 터미널에서 node ./bst.cjs로 실행합니다. CommonJS 한 파일에 전체 클래스와 범위 함수, 직접 실행 예제가 들어 있습니다. 재귀 대신 반복문을 사용해 한쪽으로 긴 트리도 호출 스택을 계속 늘리지 않습니다.

'use strict';

function checkKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}

function rangeValues(root, low, high) {
  checkKey(low);
  checkKey(high);
  const result = [];
  if (low > high) return result;
  const stack = [];
  let current = root;
  while (current != null || stack.length > 0) {
    while (current != null) {
      if (current.key < low) {
        current = current.right;
      } else {
        stack.push(current);
        current = current.left;
      }
    }
    if (stack.length === 0) break;
    current = stack.pop();
    if (current.key > high) break;
    for (let copy = 0; copy < current.count; copy += 1) {
      result.push(current.key);
    }
    current = current.right;
  }
  return result;
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(key) {
    checkKey(key);
    const fresh = { key, count: 1, left: null, right: null };
    if (this.root === null) {
      this.root = fresh;
      return this;
    }
    let current = this.root;
    while (true) {
      if (key === current.key) {
        current.count += 1;
        return this;
      }
      const side = key < current.key ? 'left' : 'right';
      if (current[side] === null) {
        current[side] = fresh;
        return this;
      }
      current = current[side];
    }
  }

  has(key) {
    checkKey(key);
    let current = this.root;
    while (current !== null) {
      if (key === current.key) return true;
      current = key < current.key ? current.left : current.right;
    }
    return false;
  }

  delete(key) {
    checkKey(key);
    let parent = null;
    let current = this.root;
    while (current !== null && current.key !== key) {
      parent = current;
      current = key < current.key ? current.left : current.right;
    }
    if (current === null) return false;
    if (current.count > 1) {
      current.count -= 1;
      return true;
    }

    if (current.left !== null && current.right !== null) {
      let successorParent = current;
      let successor = current.right;
      while (successor.left !== null) {
        successorParent = successor;
        successor = successor.left;
      }
      current.key = successor.key;
      current.count = successor.count;
      if (successorParent === current) {
        successorParent.right = successor.right;
      } else {
        successorParent.left = successor.right;
      }
      return true;
    }

    const child = current.left !== null ? current.left : current.right;
    if (parent === null) {
      this.root = child;
    } else if (parent.left === current) {
      parent.left = child;
    } else {
      parent.right = child;
    }
    return true;
  }

  range(low, high) {
    return rangeValues(this.root, low, high);
  }

  inorder() {
    return this.range(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
  }
}

module.exports = { BinarySearchTree, rangeValues };

if (require.main === module) {
  const tree = new BinarySearchTree();
  for (const key of [10, 5, 20, 15, 15, 17]) tree.insert(key);
  const before = tree.inorder();
  tree.delete(10);
  const afterRoot = tree.inorder();
  tree.delete(15);
  console.log(JSON.stringify({ before, afterRoot, afterOne: tree.inorder(), found: tree.has(10) }));
}

실행 출력

{"before":[5,10,15,15,17,20],"afterRoot":[5,15,15,17,20],"afterOne":[5,15,17,20],"found":false}

삽입과 탐색: 같은 비교로 같은 경로를 따라갑니다

insert는 현재 노드와 비교해 left 또는 right를 선택합니다. 빈 연결을 만나면 그 위치에 새 노드를 연결합니다. 처음부터 root가 비어 있으면 루트를 만드는 별도 분기가 필요합니다. 중복이면 count만 증가시켜 같은 키가 양쪽에 흩어지는 상황을 막습니다.

has도 같은 경로를 따르지만 연결을 만들지 않습니다. null에 도착하면 그 키가 들어갈 자리가 비었다는 뜻입니다. 검색 실패를 예외가 아니라 false로 돌려주는 이유는 정상적인 조회 결과이기 때문입니다. 반면 잘못된 키 타입은 입력 계약 위반으로 예외를 던집니다.

삭제는 어느 연결을 다시 이어야 하는가

삭제 대상을 찾는 동안 parent를 함께 기억합니다. 목표 노드가 없어졌을 때 부모가 어느 자식을 가리켜야 하는지 바꾸기 위해서입니다. 대상이 루트인 경우에는 부모가 없으므로 this.root 자체를 교체해야 합니다. 이 구분을 놓치면 루트 삭제만 실패합니다.

자식이 둘이면 한쪽만 부모에 연결할 수 없으므로 중위 후계자를 사용합니다. 오른쪽 부분 트리에서 가장 왼쪽에 있는 노드는 대상보다 큰 키 중 최솟값입니다. 후계자에게 왼쪽 자식은 없으므로 그 노드의 제거는 오른쪽 자식 하나를 올려 잇는 문제로 줄어듭니다.

중복 정책 때문에 후계자의 key뿐 아니라 count 전체를 옮깁니다. 예를 들어 15가 두 개면 현재 노드에 15×2를 담고 원래 후계자 노드는 통째로 제거합니다. 일반 delete(15)를 한 번 호출해 count만 줄이면 두 노드에 같은 키가 남아 엄격한 순서 불변식이 깨집니다.

후계자가 바로 오른쪽 자식이면 successorParent가 current입니다. 이때는 current.right를 후계자의 오른쪽 자식으로 바꿉니다. 더 깊은 왼쪽 경로에 있었다면 successorParent.left를 바꿉니다. 두 경우를 분리해야 바로 옆 후계자에서 자기 참조나 연결 손실이 생기지 않습니다.

범위 검색은 중위 순회에서 불가능한 가지를 건너뜁니다

rangeValues에서 current.key < low이면 그 노드와 왼쪽 전체가 범위 밖이므로 오른쪽으로 바로 이동합니다. 나머지는 왼쪽을 먼저 방문하는 중위 순서로 스택에 쌓습니다. 꺼낸 키가 high를 넘으면 이후 키도 모두 더 크므로 전체 반복을 끝냅니다. 범위 안의 키는 count번 출력합니다.

inorder는 안전 정수 전체를 범위로 지정해 같은 함수를 재사용합니다. 별도 중위 구현을 복사하지 않으므로 중복 확장 규칙이 서로 달라지지 않습니다. 다만 count가 매우 크면 반환 배열도 그만큼 커지므로 키별 개수만 필요할 때는 [key,count] 형태로 반환하는 별도 API가 적합합니다.

최악 O(n)을 숨기지 않는 복잡도

u는 서로 다른 키 수, n은 count 합, h는 높이입니다. 삽입 순서가 1,2,3,…이면 높이가 u-1인 연결 리스트 같은 모양이 됩니다. 균형 잡힌 모양이나 특정 무작위 삽입 모델에서 평균 로그 높이를 기대할 수 있지만, 이 삭제 방식을 반복한다고 균형이 보장되지는 않습니다. 최악 로그 시간이 필요하면 AVL이나 레드-블랙 트리를 선택해야 합니다.

경계 확인과 연습

리프 삭제, 한 자식 삭제, 루트 삭제, 바로 오른쪽인 후계자, 깊은 후계자와 중복 count를 별도로 확인하세요. 매 연산 후 중위 결과를 정렬된 다중집합과 비교하면 개수 유실을 찾을 수 있고, 모든 노드의 좌우 범위를 재검사하면 중복 키가 두 노드에 나뉜 오류도 찾을 수 있습니다.

함께 연습하고 확인할 자료

Delete Node in a BST: BST 노드 삭제를 연습하는 외부 문제입니다. 이 글의 count 중복 정책과 달리 공식 입력의 키 조건을 따르세요.

관련 개념 참고: Princeton Algorithms — Binary Search Trees 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.