[DataStructure] 트리

[트리]

트리

• 트리(tree) : 주로 계층적인 구조를 표현하기 위한 자료구조
• 노드(node) : 데이터를 저장하는 구성 요소
• 간선(edge) : 노드와 노드를 연결하는 선, 링크라고도 함
  • 링크로 연결된 노드는 상하 관계 형성

용어	설명
부모 노드(parent node)	어떤 노드의 상위에 연결된 노드
자식 노드(child node)	어떤 노드의 하위에 연결된 노드
형제 노드(sibling node)	같은 부모 노드를 공유하는 노드
조상 노드(ancestor node)	부모 노드와 그 부모 노드들
자손 노드(descendant node)	자식 노드와 그 자식 노드들
루트 노드(root node)	트리의 최상위 노드, 부모 노드가 없는 노드
리프 노드(leaf node)	트리의 최하위 노드, 자식 노드가 없는 노드
차수(degree)	어떤 노드가 가지고 있는 자식 노드의 수
레벨(level)	루트 노드에서 시작해 특정 노드에 이르기까지 거치게 되는 간선의 수
- 서브 트리(subtree) : 트리에 포함되어 있는 부분

• 트리 자료구조의 메모리 상 구조
  • 데이터를 저장할 공간과 자식 노드의 위치 정보(메모리 상의 주소)를 저장할 공간의 모음
  

---

[트리의 순회]

트리의 순회

• 트리 순회(tree traversal): 트리의 모든 노드를 한 번씩 방문하는 것
• 대표적인 트리 순회 방법
  • 전위 순회
  • 중위 순회
  • 후위 순회

전위 순회

• 전위 순회(preorder traversal) : 루트 노드 → 왼쪽 서브트리 전위 순회 → 오른쪽 서브트리 전위 순회
  
• 전위 순회(노드): if 노드가 존재하지 않으면: return 노드 값 출력 전위 순회(노드의 왼쪽 자식) 전위 순회(노드의 오른쪽 자식)

중위 순회

• 중위 순회(inorder traversal) : 왼쪽 서브트리 중위 순회 → 루트 노드 → 오른쪽 서브트리 중위 순회
  
• 중위 순회(노드): if 노드가 존재하지 않으면: return 중위 순회(노드의 왼쪽 자식) 노드 값 출력 전위 순회(노드의 오른쪽 자식)

후위 순회

• 후위 순회(postorder traversal) : 왼쪽 서브트리 후위 순회 → 오른쪽 서브트리 후위 순회 → 루트 노드
  
• 후위 순회(노드): if 노드가 존재하지 않으면: return 후위 순회(노드의 왼쪽 자식) 후위 순회(노드의 오른쪽 자식) 노드 값 출력

레벨 순서 순회

• 레벨 순서 순회(level-order traversal) : 가장 낮은 레벨부터 순회
  • DFS와 BFS에 주로 사용

---

[트리의 종류]

이진 트리

• 이진 트리(binary tree) : 자식 노드의 개수가 2개 이하인 트리

• 편향된 이진 트리(skewed binary tree) : 모든 자식 노드가 한 쪽으로 치우친 이진 트리
• 정 이진 트리(full binary tree) : 자식 노드 개수가 1개가 아닌 이진 트리 (0개 또는 2개)
• 포화 이진 트리(perfect binary tree) : 리프 노드를 제외한 모든 노드들이 자식 노드 2개이며, 모든 리프 노드의 레벨이 동일한 이진 트리

• 완전 이진 트리(complete bianry tree) : 마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드를 가지며, 마지막 레벨의 모든 노드들이 왼쪽부터 존재하는 이진 트리

탐색에 활용되는 트리: 이진 탐색 트리와 힙

• 이진 탐색 트리(Binary Search Tree) : 특정 노드의 왼쪽 서브트리에 해당 노드보다 작은 값을 지닌 노드 존재, 오른쪽 서브 트리에는 해당 노드보다 큰 값을 지닌 노드 존재
  • BST 시간 복잡도 : O(log n)
  • BST (편향 트리) 시간 복잡도 : O(n) → BST 중 최악의 상황
• 최대 힙 : 부모 노드가 자식 노드의 값보다 큰 값으로 이루어진 이진 트리
  • 시간 복잡도 : O(log n)
• 최소 힙 : 부모 노드가 자식 노드의 값보다 작은 값으로 이루어진 이진 트리
  • 시간 복잡도 : O(log n)