[javascript] 트리 (Tree) 데이터 구조

08 Dec 2023

javascript

트리는 계층적인 데이터를 나타내는 일반적인 데이터 구조입니다. 트리는 부모-자식 관계로 이루어진 노드들의 집합으로 표현됩니다.

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있습니다.

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

이진 트리의 노드는 위와 같이 JavaScript 클래스로 구현할 수 있습니다.

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 모든 왼쪽 자식 노드의 값이 해당 노드의 값보다 작고, 모든 오른쪽 자식 노드의 값이 해당 노드의 값보다 큰 이진 트리입니다. 이러한 속성으로 인해 효과적인 탐색이 가능합니다.

function insertNode(root, value) {
  if (!root) {
    return new Node(value);
  }

  if (value < root.value) {
    root.left = insertNode(root.left, value);
  } else if (value > root.value) {
    root.right = insertNode(root.right, value);
  }

  return root;
}

위의 예제는 이진 탐색 트리에 노드를 삽입하는 JavaScript 함수를 보여줍니다.

이처럼 트리는 다양한 응용 분야에서 효율적인 데이터 구조로 활용됩니다.

참고 문헌

Introduction to Algorithms, Cormen et al. (2009)
JavaScript Data Structures and Algorithms, Sammie Bae (2019)

위 참고 문헌에서 더 많은 내용을 찾아볼 수 있습니다.