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

이진 탐색 트리가 필요한 이유

이진 탐색 알고리즘의 한계

이진 탐색은 O(log n)의 빠른 탐색 성능을 제공하지만 치명적인 단점이 있다

• 배열이 정렬되어 있어야 함
• 배열은 데이터 삽입/삭제가 비효율적 (O(n))

해시 테이블은 어떨까?

해시 테이블도 좋은 대안이지만 나름의 단점이 있다

장점	단점
삽입/삭제/검색 모두 빠름 (평균 O(1))	성능이 해시 함수 품질에 의존
	더 많은 메모리 필요
	데이터가 정렬되지 않음

이진 탐색 트리의 등장

이진 탐색 트리는 이진 탐색의 빠른 탐색 성능과 효율적인 삽입/삭제를 동시에 제공한다.

        18
       /  \
      15   31
     /    /  \
    10   27   33
   / \   /      \
  6  12 24      35
 / \  /  \       \
3  8 11  20      37

장점

• 탐색/삽입/삭제 모두 O(log n) (균형 잡힌 경우)
• 데이터가 자동으로 정렬된 상태 유지
• 해시 테이블보다 메모리 효율적

 

이진 탐색 트리의 규칙

BST는 이진 트리에 정렬 규칙을 추가한 자료구조다.

1. 중복된 노드가 없어야 함
2. 왼쪽 서브트리: 현재 노드보다 작은 값들만
3. 오른쪽 서브트리: 현재 노드보다 큰 값들만
4. 모든 서브트리에도 위 규칙이 재귀적으로 적용

올바른 BST

     10
    /  \
   5    15
  / \   / \
 3   7 12  20

잘못된 BST (12가 10보다 큼)

     10
    /  \
   5    15
  / \   / \
 3  12 7   20

 

주요 연산

1. 탐색 (Search)

루트부터 시작해 값을 비교하며 왼쪽/오른쪽으로 이동한다.

search(targetData) {
  let currentNode = this.root;

  while (currentNode != null) {
    if (currentNode.getData() == targetData) {
      return currentNode;  // 찾음
    } else if (currentNode.getData() > targetData) {
      currentNode = currentNode.getLeftSubTree();  // 왼쪽으로
    } else {
      currentNode = currentNode.getRightSubTree();  // 오른쪽으로
    }
  }

  return null;  // 없음
}

• 시간 복잡도: O(log n) - 균형 잡힌 경우

2. 삽입 (Insert)

탐색과 비슷하게 적절한 위치를 찾아 삽입한다.

insert(data) {
  if (this.root == null) {
    this.root = new BinaryTree(data);
    return;
  }

  let currentNode = this.root;
  let parentNode = null;

  // 삽입 위치 찾기
  while (currentNode != null) {
    parentNode = currentNode;

    if (currentNode.getData() > data) {
      currentNode = currentNode.getLeftSubTree();
    } else if (currentNode.getData() < data) {
      currentNode = currentNode.getRightSubTree();
    } else {
      return;  // 중복 값은 삽입하지 않음
    }
  }

  // 새 노드 삽입
  let newNode = new BinaryTree(data);
  if (parentNode.getData() > data) {
    parentNode.setLeftSubTree(newNode);
  } else {
    parentNode.setRightSubTree(newNode);
  }
}

• 시간 복잡도: O(log n)

3. 삭제 (Remove)

Case 1: 리프 노드 삭제

자식이 없으면 그냥 제거한다.

     10              10
    /  \            /  \
   5    15   →     5    15
  / \              /
 3   7            7

Case 2: 자식이 하나인 노드 삭제

자식 노드를 부모에 직접 연결한다.

     10              10
    /  \            /  \
   5    15   →     7    15
    \
     7

Case 3: 자식이 둘인 노드 삭제

대체 노드를 찾아야 한다.

두 가지 선택지:

• 왼쪽 서브트리의 최댓값
• 오른쪽 서브트리의 최솟값

     10              12
    /  \            /  \
   5    15   →     5    15
  / \   / \       / \   / \
 3   7 12  20    3   7 11  20
      /
     11

 

사용 예제

let bst = new BinarySearchTree();

// 데이터 삽입
bst.insert(18);
bst.insert(15);
bst.insert(10);
bst.insert(31);

// 중위 순회 - 오름차순 정렬된 결과
bst.root.inOrderTraversal(bst.root); // 10, 15, 18, 31

// 탐색
console.log(bst.search(15)); // 노드 반환
console.log(bst.search(100)); // null

// 삭제
bst.remove(15);
bst.root.inOrderTraversal(bst.root); // 10, 18, 31

 

시간 복잡도

연산	평균 (균형)	최악 (편향)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

트리의 균형이 중요한 이유

균형 잡힌 트리

      4
     / \
    2   6
   / \ / \
  1  3 5  7

• 높이: 3, 탐색: O(log n)

편향된 트리 (최악)

1
 \
  2
   \
    3
     \
      4
       \
        5

• 높이: 5, 탐색: O(n) - 사실상 연결 리스트

 

자가 균형 이진 탐색 트리

위 내용과 같이 BST의 성능을 보장하려면 균형이 필수이다.

삽입/삭제 시 균형을 깨트리지 않기 위해 고안해낸 트리들이 있는데, 다음과 같은 트리들을  자가 균형 이진 탐색 트리(Self-Balancing BST) 라고 부른다.

• AVL 트리: 엄격한 균형 유지
• Red-Black 트리: 느슨한 균형, 삽입/삭제 빠름
• B-트리: 데이터베이스에서 사용