javascript - 트리(Tree)

트리(Tree)

계층적인 구조를 표현하는 추상 자료형입니다. 트리는 노드들의 집합과 이들을 연결하는 간선들의 집합으로 구성되며, 한 노드가 다른 노드를 가리키는 방향성을 가진다는 점에서 그래프의 한 종류라고 할 수 있습니다. 트리에서는 노드가 자식 노드를 여러 개 가질 수 있지만, 한 노드가 여러 부모 노드를 가질 수는 없습니다.

 

루트(Root): 트리의 최상위 노드입니다. 트리는 하나의 루트 노드만을 가집니다.
부모(Parent): 어떤 노드의 직속 상위 노드를 그 노드의 '부모'라고 합니다.
자식(Child): 어떤 노드의 직속 하위 노드를 그 노드의 '자식'이라고 합니다.
형제(Sibling): 같은 부모 노드를 공유하는 노드들을 '형제'라고 합니다.
리프 노드(Leaf Node): 자식이 없는 노드를 '리프 노드' 혹은 '단말 노드'라고 합니다.
내부 노드(Internal Node): 적어도 하나 이상의 자식을 가지는 노드를 '내부 노드'라고 합니다.
레벨(Level): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 그 노드의 '레벨'이라고 합니다. 루트 노드의 레벨은 0입니다.
높이(Height): 트리의 '높이'는 트리의 최대 레벨입니다.

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

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

  // 노드 추가, 검색 등의 메서드를 이곳에 구현할 수 있습니다.
}

// 사용 예시
let tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

위의 코드는 매우 간단한 이진 트리를 구현한 예제입니다. 노드에 데이터를 저장하고, 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드에 대한 참조를 가집니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.

트리는 파일 시스템, HTML DOM(Document Object Model), 데이터베이스 인덱스, 라우팅 알고리즘 등 많은 분야에서 사용되며, 또한 트리를 기반으로 한 여러 가지 특수한 자료구조들(예: 이진 검색 트리, 힙, 트라이 등)이 있습니다.

트리의 종류

일반 트리(General Tree): 가장 기본적인 형태의 트리로, 노드는 0개 이상의 자식 노드를 가질 수 있습니다.

이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분됩니다.

완전 이진 트리(Complete Binary Tree): 위에서 아래로, 왼쪽에서 오른쪽으로 노드가 순차적으로 채워진 이진 트리입니다. 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨에 노드가 있는 경우 왼쪽에서부터 차례대로 채워져야 합니다.

완전히 균형 이진 트리(Perfect Binary Tree): 모든 내부 노드가 두 개의 자식 노드를 가지고, 모든 리프 노드가 같은 레벨에 있는 이진 트리입니다.

균형 트리(Balanced Tree): 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 많아야 1인 이진 트리입니다. 이를 만족하는 트리를 AVL 트리라고도 합니다.

이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 큰 특징을 가진 이진 트리입니다.

힙(Heap): 완전 이진 트리의 일종으로, 각 노드의 키 값이 그의 부모 노드의 키 값보다 크거나 같다면 최대 힙(max heap), 작거나 같다면 최소 힙(min heap)이라고 합니다.

B-트리(B-tree): 데이터베이스나 파일 시스템에서 사용되는 자료구조로, 노드 내에 여러 개의 키를 가질 수 있고 노드의 자식 수가 노드의 키 수보다 항상 1개 더 많은 특징을 가집니다.

트라이(Trie): 텍스트 검색을 위해 사용되는 특수한 트리 구조로, 트리의 각 노드는 하나의 알파벳 문자를 저장하고, 문자열은 루트 노드에서부터 한 노드씩 따라가면서 구성됩니다.

레드-블랙 트리(Red-Black Tree): 균형 이진 탐색 트리의 일종으로, 노드에 색깔(레드 또는 블랙)을 추가하여 특정 규칙을 만족시킴으로써 트리의 균형을 유지합니다.