[자료구조](9)[트리&이진트리]

기존까지 다뤘던 배열, 연결 리스트, 스택, 큐는 선형 자료구조!

트리

• 특징
  부모-자식 관계
      root 노드를 제외하면 전부 부모 가짐
      leaf 노드를 제외하면 전부 자식 가짐
• 계층의 분화가 일어난다: 여러 레벨로 데이터가 구조화된다.
  탐색에 효율적임: O(logn)
  효율적인 삽입 연산
  현실 반영을 잘 함: 실제 현실의 구조와 많이 비슷함
  선형 구조보다 더 복잡한 구조 표현 가능

배열과 연결 리스트의 단점 보완

트리 ADT

• 노드: 데이터가 저장된 요소
• 엣지: 노드 사이를 잇는 선

용어

• 뿌리(root), 잎(leaf), 비단말(non-terminal)
  뿌리: 맨 위에 있는 노드
  잎: 맨 끝에 있는 자식이 없는 노드
  비단말: 뿌리도 잎도 아닌 노드
• 부모(parent), 자식(child), 형제(sibling):
  부모: 어떤 노드를 가리키는 노드 (부모는 항상 1개)
  자식: 가리켜지는 노드
  형제: 같은 부모에서 나온 노드
• 조상(ansestor), 후손(descendant)
  조상: 현재 노드에서부터 뿌리까지 거슬러 올라가는 모든 노드
  후손: 현재 노드에서부터 아래로 도달할 수 있는 모든 노드
• 차수(degree): 자식 노드의 갯수
• 레벨(level): 뿌리 노드로부터 거리
  뿌리 = 1 여기서부터 시작
• 높이(height): 잎으로 가는 가장 긴 거리의 엣지 수
• 부분트리(subtree): 다른 노드를 뿌리 노드로 잡고 만든 트리
  모든 트리는 subtree로 쪼개질 수 있다
  예)

뿌리: A
잎: C, F, G, I, J, K, L
H 의 부모: D
B 의 자식: E, F
J 의 형제: K, L
G 의 조상: A, D
D 의 후손: G, H, I, M
A 의 차수: 3
I 의 레벨: 3
G 의 높이: 0

이진트리

degree가 2 이하인 트리
(= 자식의 수가 2 이하인 트리)
-> 이진트리의 모든 subtree는 항상 이진트리

이진트리의 노드 수와 높이
노드가 N개 있을 때,

• 최소 높이: floor(log2 N)
• 최대 높이: N-1
  높이가 H일때,
• 최소 노드 수: H+1
• 최대 노드 수: 2^(H+1)-1

이진트리의 종류

포화 이진트리(full): 모든 노드의 차수가 0 or 2
완전 이진트리(complete): 맨 마지막을 제외하면 다 채워짐 & 왼쪽->오른쪽으로 채워짐
완전 포화 이진트리(perfect): 전부 다 채워짐
균형 이진트리(balanced): 모든 subtree의 height 차가 1 이하
편향 이진트리(degenerate or skewed): 모든 노드가 자식을 1개만 가짐