[CS - 자료구조] 트리 (Tree), 이진 트리 (Binary Tree)

트리 (Tree)

• 개념
  • 선형 구조인 큐, 스택과 달리, 비선형 구조로 계층적 관계(Hierarchiral Relationship)를 표현하며 데이터를 저장하는 자료구조
  • 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프 (자기 자신으로 돌아오지 않는)

 

• 용어
  • 노드 (Node) : 트리를 구성하는 각각의 요소
  • 간선 (Edge) : 노드를 연결하는 선
  • 루트 노드 (Root Node) : 트리 구조에서 최상위에 있는 노드
  • 단말 노드 (Leaf Node 또는 Terminal Node) : 하위에 다른 노드가 없는 노드 (맨 끝에 있는 노드)
  • 내부 노드 or 비단말 노드 (Internal Node) : 단말 노드를 제외한 모든 노드 (루트 노드도 포함)
  • 레벨 (Level) : 노드가 몇 층인지 나타냄 (루트 노드의 레벨은 0)
  • 깊이 (Depth) : 출발 노드 ~ 도착 노드 간에 연결된 노드 수
  • 높이 (Height) : 루트 노드로부터 가장 깊숙이 있는 노드의 깊이
  • 크기 (Size) : 해당 레벨의 노드 수
  • 너비 (Width) : 최대 크기 (제일 노드 수가 많은 층의 크기)

 

이진 트리 (Binary Tree)

• 배경
  • 트리의 자식 노드가 여러개라면, 구현하기가 굉장히 복잡하고 어려움
  • 실질적으로 트리를 활용하기 위해 자식 노드를 2개 이하로 제한된 이진 트리가 많이 사용됨

 

• 개념
  • 모든 노드의 자식 노드가 2개 이하인 트리
  • 이 두개의 자식 노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 나눌 수 있음

 

• 종류
  • 전 이진 트리 (Full Binary Tree)
    • 자식 노드가 0개 또는 2개로만 이루어진 이진 트리 (자식 노드가 1개인 노드는 없음)
  • 완전 이진 트리 (Complete Binary Tree)
    • 마지막 레벨을 제외한 모든 레벨의 노드는 가득 차있어야 하고, 마지막 레벨은 왼쪽에서부터 채워져있는 이진 트리 (순서를 잘 지킨 이진 트리)
  • 포화 이진 트리 (Perfect Binary Tree)
    • 정 이진 트리이면서 완전 이진 트리인 트리. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 차있음 (빈 공간이 없는 이진 트리)