[자료구조] 트리(Tree)란? 🌲🌲

트리(Tree)

• 트리는 계층적인 자료를 표현하는데 적합한 자료구조이다.
• 데이터의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.

트리의 용어

• 노드 (Node): 트리를 구성하고 있는 각 요소
  • ex) A, B, C ... J, K
• 간선 (Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node: 최상위 계층에 존재하는 노드
  • ex) A
• Level: 트리의 특정 깊이를 가지는 노드의 집합
  • ex) A의 level은 1, E의 level은 3
• 차수 (Degree): 어떤 노드가 가지고 있는 자식 노드의 개수
  • ex) B의 차수는 2, D의 차수는 3
• 깊이 (Depth, Height): 어떤 트리에서 노드가 가질 수 있는 최대의 레벨
  • ex) 위의 트리에서 깊이는 4
• 단말 노드(Terminal Node = Leaf Node): 자식이 하나도 없는 노드
  • ex) C, E, F, H, I, J, K
• 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드
  • ex) A, B, D, G
• 자식 노드(Child Node): 어떤 노드에 연결된 다음 레벨의 노드
  • ex) B의 자식 노드는 E, F
• 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드
  • ex) H의 부모 노드는 D
• 형제 노드(Sibling Node): 동일한 부모를 갖는 노드
  • ex) J의 형제 노드는 K

이진트리 (Binary Tree)

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리라고 한다.
• 서브 트리는 공집합일 수 있다.
• 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다.
• 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2 ^ i 이다. (i >= 0)
• 깊이(level)이 k인 이진트리가 가질 수 있는 최대 노드의 수는 2 ^ k-1 이다. (ㅏ >= 1)

이진 트리는 완전 이진트리(Complete binary tree)와 포화 이진트리(Perfect binary tree), 균형 이진트리(Full binary tree)라고 하는 트리 구조를 정의할 수 있다.

완전 이진 트리 (Complete binary tree)

• 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.
• 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈 곳이 있어서는 안된다.
• 포화 이진트리는 항상 완전 이진트리이지만 그 역은 항상 성립하지 않는다.
• 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1이하이다.

균형 이진 트리(Full binary tree, 전 이진 트리)

• 모든 노드가 0개 또는 2개의 자식 노드를 가지고 있는 트리이다.
  

  

포화 이진 트리(Perfect binary tree)

• 각 레벨에 노드가 꽉 차있는 이진트리를 의미한다.
• 높이 k인 포화 이진트리는 2^k -1개의 노드를 가진다.
• 전 이진 트리이면서 완전 이진 트리인 경우를 의미한다.