Binary Search Tree를 구현해보기 (TypeScript)

최근에 Typescript로 BST를 직접 구현해 보라는 질문을 받았는데 제대로 구현하지 못했다. 그래서 중요한 개념을 복습할 겸 하나씩 정리해 보고자 한다. with Codex

이 글은 정수 값만 저장하는 Binary Search Tree(BST) 를 TreeNode, BinarySearchTree 두 클래스로 직접 구현하는 흐름을 정리한 노트입니다. 먼저 의사코드로 생각을 고정하고, 그 다음 그림으로 포인터 이동을 확인한 뒤, 마지막에 TypeScript 코드로 옮깁니다.

이 구현의 규칙은 네 가지입니다.

• value는 정수만 허용합니다.
• 한 노드의 왼쪽 서브트리에는 더 작은 값만 둡니다.
• 한 노드의 오른쪽 서브트리에는 더 큰 값만 둡니다.
• 중복 값은 삽입하지 않고 false를 반환합니다.

1. BST 규칙부터 잡기

BST는 이름 그대로 “검색을 빠르게 하기 위한 이진 트리”입니다. 핵심은 노드 하나를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 둔다는 점입니다.

의사코드로 쓰면 이렇게 시작할 수 있습니다.

BST 규칙

어떤 node가 있을 때
  node.left에 있는 모든 값은 node.value보다 작다
  node.right에 있는 모든 값은 node.value보다 크다

값을 찾거나 넣을 때
  비교 대상 value가 node.value보다 작으면 왼쪽으로 간다
  비교 대상 value가 node.value보다 크면 오른쪽으로 간다
  같으면 찾은 것이다

이 규칙 덕분에 모든 노드를 무조건 훑지 않고, 비교할 때마다 탐색 범위를 왼쪽 또는 오른쪽으로 줄일 수 있습니다.

2. 클래스 책임 나누기

TreeNode는 값 하나와 왼쪽/오른쪽 포인터를 책임지고, BinarySearchTree는 루트 노드와 삽입, 검색, 삭제, 순회 같은 동작을 책임집니다.

먼저 TreeNode 의사코드는 단순합니다.

CLASS TreeNode
  value
  left
  right

  CONSTRUCTOR(value)
    if value is not integer
      throw error

    this.value = value
    this.left = null
    this.right = null

TypeScript에서는 number 타입만으로 정수를 보장할 수 없습니다. 1.5도 number이기 때문입니다. 그래서 런타임에서 Number.isInteger(value)로 한 번 더 검사합니다.

function assertInteger(value: number): void {
  if (!Number.isInteger(value)) {
    throw new TypeError("value must be an integer");
  }
}

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    assertInteger(value);
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

3. insert(value) 의사코드

삽입은 루트부터 시작해서 비교하며 내려갑니다. 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽입니다. 내려가다가 null 포인터를 만나면 그 자리가 새 노드의 위치입니다.

METHOD insert(value)
  if value is not integer
    throw error

  if root is null
    root = new TreeNode(value)
    return true

  current = root

  LOOP
    if value == current.value
      return false

    if value < current.value
      if current.left is null
        current.left = new TreeNode(value)
        return true

      current = current.left
    else
      if current.right is null
        current.right = new TreeNode(value)
        return true

      current = current.right

이 의사코드를 그대로 TypeScript로 바꾸면 다음과 같습니다.

insert(value: number): boolean {
  assertInteger(value);

  if (this.root === null) {
    this.root = new TreeNode(value);
    return true;
  }

  let current: TreeNode = this.root;

  while (true) {
    if (value === current.value) {
      return false;
    }

    if (value < current.value) {
      if (current.left === null) {
        current.left = new TreeNode(value);
        return true;
      }

      current = current.left;
    } else {
      if (current.right === null) {
        current.right = new TreeNode(value);
        return true;
      }

      current = current.right;
    }
  }
}

while (true)를 써도 괜찮은 이유는 내부에서 반드시 return하는 조건이 있기 때문입니다. 빈 자리를 찾으면 true, 중복 값을 만나면 false로 끝납니다.

4. contains(value) 의사코드

검색은 삽입보다 더 단순합니다. 새 노드를 만들지 않고, 같은 비교 규칙으로 내려가면서 값이 있는지만 확인합니다.

METHOD contains(value)
  if value is not integer
    throw error

  current = root

  while current is not null
    if value == current.value
      return true

    if value < current.value
      current = current.left
    else
      current = current.right

  return false

TypeScript 코드입니다.

contains(value: number): boolean {
  assertInteger(value);

  let current = this.root;

  while (current !== null) {
    if (value === current.value) {
      return true;
    }

    current = value < current.value ? current.left : current.right;
  }

  return false;
}

current가 null이 되었다는 것은 더 내려갈 자식이 없다는 뜻입니다. 즉, 그 값은 트리에 없습니다.

5. remove(value) 의사코드

삭제는 삽입/검색보다 한 단계 어렵습니다. 삭제할 노드의 자식 개수에 따라 처리가 달라지기 때문입니다.

세 경우만 기억하면 됩니다.

• 자식이 없으면 부모가 그 자리를 null로 바꿉니다.
• 자식이 하나면 삭제할 노드 대신 그 자식을 부모에게 연결합니다.
• 자식이 둘이면 오른쪽 서브트리에서 가장 작은 값, 즉 successor를 찾아 현재 노드의 값으로 복사한 뒤 successor 원본 노드를 삭제합니다.

METHOD remove(value)
  root, removed = removeNode(root, value)
  return removed

METHOD removeNode(node, value)
  if node is null
    return null, false

  if value < node.value
    node.left, removed = removeNode(node.left, value)
    return node, removed

  if value > node.value
    node.right, removed = removeNode(node.right, value)
    return node, removed

  // 여기까지 왔다면 node.value == value

  if node has no child
    return null, true

  if node has only right child
    return node.right, true

  if node has only left child
    return node.left, true

  successor = find minimum node in node.right
  node.value = successor.value
  node.right, _ = removeNode(node.right, successor.value)
  return node, true

삭제는 부모 포인터를 직접 들고 다니는 방식으로도 구현할 수 있습니다. 여기서는 재귀 함수가 “삭제 후 이 자리에 다시 연결할 노드”를 반환하게 만들었습니다. 그래서 루트를 삭제하는 경우도 같은 코드로 처리됩니다.

6. traversal 의사코드

순회는 트리의 모든 값을 어떤 순서로 방문할지 정하는 규칙입니다. BST에서 가장 자주 쓰는 것은 inOrder입니다. 왼쪽 → 현재 노드 → 오른쪽 순서로 방문하면 값이 오름차순으로 나옵니다.

METHOD inOrder()
  result = []

  FUNCTION walk(node)
    if node is null
      return

    walk(node.left)
    result.push(node.value)
    walk(node.right)

  walk(root)
  return result

preOrder와 postOrder는 방문 위치만 바뀝니다.

preOrder:  node → left → right
inOrder:   left → node → right
postOrder: left → right → node

7. 최종 TypeScript 구현

아래 코드는 위 의사코드를 하나로 합친 완성본입니다.

function assertInteger(value: number): void {
  if (!Number.isInteger(value)) {
    throw new TypeError("value must be an integer");
  }
}

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    assertInteger(value);
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  root: TreeNode | null;

  constructor() {
    this.root = null;
  }

  insert(value: number): boolean {
    assertInteger(value);

    if (this.root === null) {
      this.root = new TreeNode(value);
      return true;
    }

    let current: TreeNode = this.root;

    while (true) {
      if (value === current.value) {
        return false;
      }

      if (value < current.value) {
        if (current.left === null) {
          current.left = new TreeNode(value);
          return true;
        }

        current = current.left;
      } else {
        if (current.right === null) {
          current.right = new TreeNode(value);
          return true;
        }

        current = current.right;
      }
    }
  }

  contains(value: number): boolean {
    assertInteger(value);

    let current = this.root;

    while (current !== null) {
      if (value === current.value) {
        return true;
      }

      current = value < current.value ? current.left : current.right;
    }

    return false;
  }

  remove(value: number): boolean {
    assertInteger(value);

    const [nextRoot, removed] = this.removeNode(this.root, value);
    this.root = nextRoot;
    return removed;
  }

  inOrder(): number[] {
    const result: number[] = [];

    const walk = (node: TreeNode | null): void => {
      if (node === null) {
        return;
      }

      walk(node.left);
      result.push(node.value);
      walk(node.right);
    };

    walk(this.root);
    return result;
  }

  preOrder(): number[] {
    const result: number[] = [];

    const walk = (node: TreeNode | null): void => {
      if (node === null) {
        return;
      }

      result.push(node.value);
      walk(node.left);
      walk(node.right);
    };

    walk(this.root);
    return result;
  }

  postOrder(): number[] {
    const result: number[] = [];

    const walk = (node: TreeNode | null): void => {
      if (node === null) {
        return;
      }

      walk(node.left);
      walk(node.right);
      result.push(node.value);
    };

    walk(this.root);
    return result;
  }

  private removeNode(node: TreeNode | null, value: number): [TreeNode | null, boolean] {
    if (node === null) {
      return [null, false];
    }

    if (value < node.value) {
      const [nextLeft, removed] = this.removeNode(node.left, value);
      node.left = nextLeft;
      return [node, removed];
    }

    if (value > node.value) {
      const [nextRight, removed] = this.removeNode(node.right, value);
      node.right = nextRight;
      return [node, removed];
    }

    if (node.left === null && node.right === null) {
      return [null, true];
    }

    if (node.left === null) {
      return [node.right, true];
    }

    if (node.right === null) {
      return [node.left, true];
    }

    const successor = this.findMinNode(node.right);
    node.value = successor.value;

    const [nextRight] = this.removeNode(node.right, successor.value);
    node.right = nextRight;

    return [node, true];
  }

  private findMinNode(node: TreeNode): TreeNode {
    let current = node;

    while (current.left !== null) {
      current = current.left;
    }

    return current;
  }
}

8. 사용 예시

const bst = new BinarySearchTree();

for (const value of [8, 3, 10, 1, 6, 14, 4, 7, 13]) {
  bst.insert(value);
}

console.log(bst.inOrder());
// [1, 3, 4, 6, 7, 8, 10, 13, 14]

console.log(bst.contains(6));
// true

console.log(bst.contains(5));
// false

console.log(bst.insert(6));
// false: 중복 값은 삽입하지 않음

console.log(bst.remove(3));
// true

console.log(bst.inOrder());
// [1, 4, 6, 7, 8, 10, 13, 14]

9. 스스로 점검할 부분

• insert에서 root === null인 첫 삽입을 따로 처리했는가?
• 작으면 왼쪽, 크면 오른쪽이라는 규칙이 insert와 contains에 똑같이 적용되는가?
• 중복 값을 어떻게 처리할지 정했는가? 이 글에서는 false를 반환합니다.
• remove에서 리프, 자식 1개, 자식 2개 케이스를 모두 처리했는가?
• inOrder() 결과가 항상 정렬된 배열인지 확인했는가?
• Number.isInteger(value)로 정수 검사를 하고 있는가?

10. 시간 복잡도

트리의 높이를 h라고 하면 insert, contains, remove는 평균적으로 O(h)입니다. 트리가 균형에 가까우면 h = log n이므로 O(log n)에 가깝고, 한쪽으로 치우치면 h = n이 되어 O(n)까지 나빠질 수 있습니다.

이 과제의 핵심은 “클래스를 만드는 법”보다 “비교 결과에 따라 포인터를 왼쪽 또는 오른쪽으로 이동시키는 감각”입니다. 그 감각만 잡히면 삽입과 검색은 거의 같은 코드로 보이고, 삭제도 세 가지 케이스로 나누어 차분히 처리할 수 있습니다.