JavaScript로 이진 탐색 트리(BST) 구현하기: 단계별 완벽 가이드

트리(Tree) 자료구조란?

트리는 여러 개의 노드가 간선(edge)으로 연결되어 있는 자료구조입니다. 일반적으로 트리의 각 노드는 데이터를 저장하며, 자식 노드에 대한 참조(reference)를 함께 가지고 있습니다.

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(BST)는 이진 트리의 한 종류로, 값이 작은 노드는 왼쪽에, 값이 큰 노드는 오른쪽에 배치하는 규칙을 따르는 트리입니다.

예를 들어, 유효한 BST의 시각적 표현은 다음과 같습니다.

     25
   /   \
  20    36
 / \   / \
10  22 30  40

이제 JavaScript 언어로 직접 이진 탐색 트리를 구현해 보겠습니다.

1단계: Node 클래스 작성

Node 클래스는 BST의 다양한 위치에 존재하는 개별 노드 하나를 나타냅니다. BST는 결국 위에서 설명한 규칙에 따라 배치된 노드들의 집합일 뿐입니다.

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

새로운 Node 인스턴스를 생성하려면 데이터를 인자로 전달하여 클래스를 호출하면 됩니다.

const newNode = new Node(23);

위 코드는 data가 23으로 설정되고, left와 right 참조가 모두 null인 새로운 노드 인스턴스를 생성합니다.

2단계: BinarySearchTree 클래스 작성

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

이렇게 만든 BinarySearchTree 클래스는 new 키워드로 호출하여 트리 인스턴스를 생성할 수 있습니다.

기본 구조가 준비되었으니, 이제 BST의 규칙에 맞는 올바른 위치에 새 노드를 삽입하는 기능을 추가해 보겠습니다.

3단계: BST에 노드 삽입하기

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

  insert(data) {
    var newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

insert 메서드는 먼저 루트가 비어 있는지 확인합니다. 비어 있다면 새 노드를 루트로 지정하고, 그렇지 않으면 insertNode 헬퍼 메서드를 호출해 재귀적으로 올바른 위치를 찾아 삽입합니다. 새 노드의 값이 현재 노드보다 작으면 왼쪽 자식을, 크거나 같으면 오른쪽 자식을 탐색합니다.

전체 코드 예제

지금까지 작성한 내용을 모두 합친 완성된 코드는 다음과 같습니다.

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

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

  insert(data) {
    var newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

이 코드를 실행하면 1, 3, 2 순서로 노드가 삽입되며, BST 규칙에 따라 1이 루트가 되고 3은 오른쪽 자식, 2는 3의 왼쪽 자식으로 배치됩니다. 이처럼 재귀적인 삽입 로직만으로도 BST의 핵심 구조를 손쉽게 구축할 수 있습니다.