트리 (Tree), 이진 트리 (Binary Tree)

트리(Tree)

• 노드와 링크로 구성된 자료구조
• Cycle이 없는 그래프의 일종 
• 계층적 구조를 나타낼 때 사용

트리의 구조

• Node : 트리 구조의 단위
• Edge : 노드 간의 연결선 (= link, branch)
• Root Node : 부모가 없는 최상위 노드
• Leaf Node : 자식이 없는 최하위 노드 (= 단말 노드)
• Internal Node : Leaf를 제외한 모든 노드
• Parent Node 
• Child Node
• Sibling Node : 같은 부모를 가지는 형제 노드
• Depth : Root 에서 어떤 노드까지의 간선 수
• Level : 트리의 특정 깊이를 가지는 노드 집합
• Height : 트리에서 가장 큰 레벨 값
• Size : 자신을 포함한 자식 노드의 개수
• Degree : 각 노드가 지닌 가지의 수
• 트리의 차수 : 트리의 최대 차수

트리의 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일
• 노드 N개인 트리의 Edge의 수 = N-1
• Acyclic
• 모든 노드는 서로 연결되어 있음
• 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

---

이진 트리 (Binary Tree)

• 각 노드가 최대 2개의 자식을 가진 트리
• 자식 노드는 좌우를 구분함

 

둘은 자식 노드 좌우가 다르기 때문에 서로 다른 이진 트리이다.

 

이진 트리 종류

• Perfect Binary Tree
  • Height가 h일 때, 수는 2^(h+1) - 1 개의 노드를 가진다( h를 0부터 시작할 때 기준)

모든 레벨에서 노드들이 꽉 채워져 있는 이진 트리

• Complete Binary Tree
  • Binary Heap 자료구조를 만들 때 사용

마지막 레벨을 제외하고 모든 레벨에서 노드가 채워져있는 이진 트리

• Full Binary Tree
  • Leaf Node의 개수 = Internal Node의 개수 + 1

모든 노드가 0개 또는 2개의 자식노드를 갖는 이진 트리

• Degenerate Tree (= Pathological Tree, Skewed Binary Tree)
  • Linked List 와 성능이 동일

한쪽으로 기울어진 트리, 모든 Internal Node가 하나의 Child만 가진다.

 

• Balanced Binary Tree
  
  • 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리

 

이진 트리 특징

• Perfect Binary Tree의 경우, 높이가 h일 때, 노드의 수 = 2^(h+1) -1
• Perfect or Complete Binary Tree의 경우, 노드가 N개 일 때, 높이는 logN
• 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N (= Degenerate Tree)

 

이진 트리의 순회 (Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 순회하는 연산
• 종류
  • DFS
    • In-order
      • 왼쪽 -> 부모 -> 오른쪽
    • Pre-order
      • 부모 -> 왼쪽 -> 오른쪽
    • Post-order
      • 왼쪽 -> 오른쪽 -> 부모
  • BFS
    • Level-order
      • 위쪽 레벨부터 왼쪽 -> 오른쪽

 

이진 트리 구현

• 배열
  • level-order 순으로 배열에 구성 (인덱스가 1번 부터 시작한다고 설정, 0으로 할 시에는 아래의 계산에다가 +1씩 더해주면된다)
  • 부모 노드의 인덱스 = 자식 노드 인덱스/ 2
  • 자식 노드의 인덱스 
    • 왼쪽 노드 = 부모노드 인덱스 * 2 
    • 오른쪽 노드  = 부모노드 인덱스 * 2 + 1

• 연결 리스트
  • 값과 간선을 관리하기 위한 노드로 연결리스트 구성