[TIL] DAY 4 - 트리(Tree)

트리 (Trees)

• 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
  • 루트(Root) 노드: 가장 꼭대기에 있는 노드
  • 리프(Leaf) 노드: 더 가지를 치지 않는 노드
  • 내부(Internal) 노드: 루트도 리프도 아닌 노드
• 노드의 수준 (Level)
  • level 0(root node)부터 시작
  • 간선의 수와 동일
• 트리의 높이 (Height)
  • 최대 수준(level) + 1
  • 깊이(depth)와 동일
• 노드의 차수 (Degree)
  
  • 자식(child)의 수와 동일
  • 리프 노드는 degree가 0

 

이진 트리 (Binary Tree)

• 모든 노드의 차수(degree)가 2 이하인 트리
• 재귀적으로 정의할 수 있음
  • 빈 트리(empty tree)이거나
  • 루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브 트리
    • 단, 이때 왼쪽과 오른쪽 서브 트리 또한 이진 트리

 

포화 이진 트리 (Full Binary Tree)

• 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
  • 높이가 k이고 노드의 개수가 2^k - 1인 이진 트리

 

완전 이진 트리(Complete Binary Tree)

• 높이 k인 완전 이진 트리
  • 레벨 k - 2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
  • 레벨 k - 1에서는 왼쪽부터 노드가 차례로 채워져 있는 이진 트리

 

출처: 프로그래머스 스쿨 17강: 트리(Trees)

 

이진 탐색 트리 (Binary Search Trees)

• 모든 노드에 대해서
  • 왼쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 작고
  • 오른쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 큰
• 성질을 만족하는 이진 트리
  • 중복되는 데이터 원소는 없는 것으로 가정
• 이진 탐색과의 비교
  • 장점: 데이터 원소의 추가, 삭제가 용이
  • 단점: 공간 소요가 큼, O(log n)의 탐색 복잡도를 가지나 항상 그런 것은 아님

 

출처: 프로그래머스 스쿨 20강: 이진 탐색 트리(Binary Search Trees)