본문으로 건너뛰기

Tree

  • 그래프는 더 일반적인 구조인 반면, 트리는 그래프의 특별한 형태
  • 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성
  • 트리는 하나의 루트 노드를 가짐
  • 트리에는 사이클(cycle)이 존재할 수 없음
  • 최하위 노드는 리프 노드(Leaf Node)
  • 그래프는 일반적인 관계를 나타내는 반면, 트리는 계층적 관계를 나타냄
  • 파일 시스템, 조직도, 문서 구조 등을 트리로 표현할 수 있다
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}

addChild(node) {
this.children.push(node);
}
}

class Tree {
constructor(rootValue) {
this.root = new TreeNode(rootValue);
}
}

순회

  • 전위 순회(Pre-order): root -> left -> right
  • 중위 순회(In-order): left -> root -> right
  • 후위 순회(Post-order): left -> right -> root
  • 레벨 순회(level-order): 위 -> 아래

binary tree

  • 자식 노드는 최대 2개
  • 포화이진트리(Perfect Binary Tree): 모든 레벨에서 노드들이 꽉 채워져 있는 트리
  • 완전이진트리(Complete Binary Tree): 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
  • 정 이진 트리 (Full binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
  • 편향 트리 (Skewed Binary Tree): 한쪽으로 기울어진 트리

binary search tree

  • 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큼
  • 중복된 값을 허용하지 않음
  • 검색, 삽입, 삭제 연산의 평균 시간 복잡도는 O(log n), 최악의 경우 O(n)

heap tree

  • 일반적으로 우선순위 큐를 구현하는데 사용되는 자료구조
  • 힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하는 데 자주 사용되는 자료구조
  • 최대 힙(Max Heap), 최소 힙(Min Heap)
  • 삽입과 삭제 연산은 O(log n)
  • 힙은 우선순위 큐, 힙 정렬, 그래프 알고리즘(다익스트라 알고리즘, 프림 알고리즘) 등에 활용