Tree 구조


트리는 위와 같은 구조를 갖고 있습니다.

용어

  • node: 트리에서 데이터를 의미
  • branch(link): 노드와 노드를 연결
  • root node: 최상위 노드
  • interior node: 자기자신 아래에 연결된 노드가 있는 형태
  • leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태
  • parent: child 노드들이 연결되어 있는 상위 노드
  • child: 부모노드 아래에 연결되어 있는 노드
  • sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드
  • degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지
  • depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수
  • level: 트리의 특정 depth를 가지는 노드의 집합
  • height: 루트노드에서부터 가장 멀리 있는 노드의 depth
  • 트리의 degree: 트리의 최대 degree
    • 위 그림에서 노드의 최대 degree는 2

Skewed Tree (Degenerate Tree)


Full (Perfect) Tree


Binary Tree

degree가 최대 2 (0 <= degree <= 2)


Quad Tree

degree가 최대 4 (0 <= degree <= 4)


정의

  • root 노드를 제외한 모든 노드는 parent 노드를 1개만 가짐
  • leaf 노드를 제외한 모든 노드는 child 노드를 1개 이상을 가짐

Tree 자료구조의 다양한 타입

Binary Tree

  • Binary Search Tree, Heap, Digital Search Tree
  • Red-Black Tree, AA Tree, Splay Tree

Height-Balanced Binary Tree

  • AVL Tree, T-Tree

n-Way Tree

  • m-Way Tree
  • 2-3 Tree, 2-3-4 Tree

Height-Balanced m-Way Tree

  • B-Tree, B+-Tree, K-d B-Tree

Spatial Tree

  • Quad Tree, Oct Tree, R-Tree


'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (2) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29