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


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

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

+ Recent posts