Tree 자료구조

트리

참고자료: https://www.youtube.com/watch?v=i5yHkP1jQmo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13

트리란...?

트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다.

트리 관련 용어

• 루트 노드(root node): 부모가 없는 최상위 노드
• 단말 노드(leaf node): 자식이 없는 노드
• 크기(size): 트리에 포함된 모든 노드의 개수
• 깊이(depth): 루트 노드부터의 거리
• 높이(height): 깊이 중 최댓값
• 차수(degree): 각 노드의 (자식 방향) 간선 개수

트리의 특징 (알고 있으면 좋은 정보)

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개이다.

이진 탐색 트리 (Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
• 이진 탐색 트리의 특징: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 부모 노드보다 왼쪽 자식 노드가 작다.
  • 부모 노드보다 오른쪽 자식 노드가 크다.

이진 탐색 트리를 만드는 방법

이상적인 경우 데이터를 탐색하는 경우 시간 복잡도는 O(logN)이다.
이상적인 경우란, 이진 탐색 트리의 왼쪽과 오른쪽이 균형이 잡혀있는 형태로 트리가 구성되어 있을 때만 가능하다.

트리의 순회 (Tree Traversal)

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미한다.
  • 트리의 정보를 시각적으로 확인할 수 있다.
• 대표적인 트리 순회 방법은 다음과 같다.
  • 전위 순회(pre-order traverse): 루트를 먼저 방문한다.
  • 중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문한다.
  • 후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문한다.