[javascript] 이진 탐색 트리 (Binary Search Tree) 데이터 구조

08 Dec 2023

javascript

이진 탐색 트리는 데이터를 저장하는 데 사용되는 효율적인 자료구조입니다. 각 노드는 최대 두 개의 자식 노드를 가질 수 있으며, 각 노드의 왼쪽 자식은 현재 노드보다 작은 값을, 오른쪽 자식은 큰 값을 가지게 됩니다.

구조

이진 탐색 트리의 각 노드는 다음과 같은 구조를 가집니다:

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

여기서 data 는 노드에 저장되는 값이며, left 와 right는 각각 왼쪽과 오른쪽 자식을 가리키는 포인터입니다.

삽입 (Insert)

이진 탐색 트리에 값이 추가될 때는 다음과 같은 과정을 거칩니다:

새로운 값을 트리에 삽입합니다.
삽입된 값이 현재 노드의 값보다 작은지 큰지를 판단하여, 적절한 위치에 삽입합니다.

다음은 삽입을 위한 간단한 자바스크립트 코드입니다:

function insert(root, data) {
  if (root === null) {
    root = new Node(data);
  } else if (data < root.data) {
    root.left = insert(root.left, data);
  } else {
    root.right = insert(root.right, data);
  }
  return root;
}

탐색 (Search)

특정 값을 가진 노드를 찾기 위해서는 다음과 같이 탐색을 수행합니다:

현재 노드의 값과 찾고자 하는 값과 비교합니다.
찾고자 하는 값이 현재 노드의 값과 같다면, 해당 노드를 반환합니다.
그렇지 않다면, 현재 노드의 값과 비교하여 왼쪽이나 오른쪽 자식 노드 중 하나를 선택하여 재귀적으로 탐색을 수행합니다.

다음은 자바스크립트 코드에서 특정 값을 가진 노드를 찾는 과정을 나타낸 것입니다:

function search(root, data) {
  if (root === null || root.data === data) {
    return root;
  }
  if (data < root.data) {
    return search(root.left, data);
  }
  return search(root.right, data);
}

참고 자료

GeeksforGeeks, “Binary Search Tree Data Structure”
MDN Web Docs, “Binary Search Tree”