[Data Structure] 트리(Tree)

트리

• 노드와 링크로 구성된 자료구조(그래프의 일종)
• 하나의 노드에서 다른 노드로의 경로는 유일
• 노드가 N개인 트리의 에지의 수는 N-1개
• 사이클이 없음
• 모든 노드가 연결되어 있음
• 계층적 구조를 나타낼 때 사용
• 에지 하나를 끊으면 2개의 서브트리로 분리됨

트리의 구조

• 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위
• 에지(Edge) : 노드 간의 연결선
• 루트 노드(Root) : 부모가 없는 노드(가장 위 노드)
• 잎새 노드(Leaf) : 자식이 없는 노드(단말 노드)
• 부모(Parent) : 연결된 두 노드 중 상위 노드
• 자식(Child) : 연결된 두 노드 중 하위 노드
• 형제(Sibling) : 같은 부모를 가지는 노드
• 깊이(Depth) : 루트에서 어던 노드까지의 간선의 수
• 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height) : 트리에서 가장 큰 레벨 값
• 차수(Degree) : 각 노드가 지닌 가지의 수

이진 트리

• 각 노드가 최대 2개의 자식을 갖음
• 자식 노드는 좌우를 분리함
• 노드가 $N$개 일 때, 최대 가능 높이는 $N-1$

이진 트리의 종류

• 포화(Perfect) 이진 트리

  • 모든 레벨에서 노드들이 꽉 채워져있는 트리
  • 높이가 $h$일 때, 노드의 수는 $2^{h+1}-1$ 개
  • 노드가 $N$일 때, 높이는 $logN$
    

• 완전(Complete) 이진 트리

  • 마지막 레벨을 제외하고 노드들이 모두 채워져있는 트리
  • 노드가 $N$일 때, 높이는 $logN$
    

• 정(Full) 이진 트리
  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
    

• 편향(Skewed) 이진 트리
  • 한쪽으로 기울어진 트리
    

이진 트리의 순회(Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
• 전위(Preorder) 순회
  • DFS
  • 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
    

• 중위(Inorder) 순회
  • DFS
  • 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
    

• 후외(Postorder) 순회
  • DFS
  • 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
    

• 레벨(Level) 순회
  • BFS
    

이진 트리의 구현

• BFS 순회 순서대로 배열로 구현
• 부모 노드가 idx일 때
  • 왼쪽 자식 노드는 idx * 2 (1-indexed 기준, 0-indexed면 +1 해줘야함)
  • 오른쪽 자식 노드는 idx * 2 + 1 (1-indexed 기준, 0-indexed면 +1 해줘야함)
  • 세그먼트 트리나 LCA 알고리즘에서 많이 쓸 인덱싱 방법