[Data Structure] Binary Search Tree

이진 탐색 트리(Binary Search Tree)는 최대 2개의 자식만 갖는 트리이다. 트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재한다. 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다.
이미지 출처: codestates urclass

이진 탐색 트리를 순회하는 방법은 크게 깊이 우선 탐색 (DFS, Depth-First Search)와 너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘이 존재한다.

깊이 우선 탐색 (DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉 한 분기의 깊이를 모두 탐색한 후, 다음 분기로 넘어간다.

1. 모든 노드를 방문하고자 할 때 사용한다.
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
3. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
4. 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

너비 우선 탐색 (BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 즉 루트 노드에서 가까운 노드를 먼저 방문하고 멀리 있는 노드를 나중에 방문한다. 노드 사이의 최단 경로를 찾고 싶을 때 사용한다.

탐색 방법

• 전위 순회(Preorder Traversal): 부모 → 좌 → 우(∠)
• 중위 순회(Inorder Traversal): 좌 → 부모 → 우(∧)
• 후위 순회(Postorder Traversal): 좌 → 우 → 부모(⦣)

이진 탐색 트리의 종류

이미지 출처: 필자 제작

• 정 이진 트리(Full Binary Tree): 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 트리. 즉 자식을 하나만 가진 노드가 없어야 함.
• 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며, 마지막 레벨의 노드도 왼쪽으로 몰려 있어야 함(부모 -> 좌 -> 우 순서로 채워짐).
• 포화 이진 트리(Perfect Binary Tree): 모든 레벨에서 노드가 꽉 차있는 트리(Complete & Full)

JS 코드 구현

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  //이진 탐색 트리에 노드를 추가
  insert(value) {
    let node = new BinarySearchTreeNode(value);
    if (this.value > value) {
      if (this.left === null) {
        this.left = node;
      } else {
        return this.left.insert(value);
      }
    }
    else if (this.value <= value) {
      if (this.right === null) {
        this.right = node;
      } else {
        return this.right.insert(value);
      }
    }
  }

  //이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환
  contains(value) {
    if (this.value === value) {
      return true;
    } else if (this.value > value) {
      if (this.left === null) {
        return false;
      } else if (this.left.contains(value)) {
        return true;
      }
    } else if (this.value <= value) {
      if (this.right === null) {
        return false;
      } else if (this.right.contains(value)) {
        return true;
      }
    }

    return false;
  }

  //이진 탐색 트리를 중위순회, 좌 -> 부모 -> 우
  inorder(callback) {
    if (this.left !== null) {
      this.left.inorder(callback);
    }
    callback(this.value);

    if (this.right !== null) {
      this.right.inorder(callback);
    }
  }
}