[알고리즘] 트리 정렬(Tree sort)

트리 정렬이란

• 이진 탐색 트리를 이용하여 정렬하는 방법이다.
• 정렬할 원소들을 이진 탐색 트리로 구성하고, 중위 우선 순회 방법을 사용한다.
• 중위 순회의 경로가 오름차순 정렬이 된다.

 

트리 정렬 수행 과정

• 정렬되지 않은 {30, 3, 49, 12, 1, 24, 5} 를 트리 정렬을 통해 과정을 살펴보자.

 

1. 정렬되지 않은 자료를 이진 탐색 트리로 구성한다.

 

 

2. 중위 순회 연산을 시행하면 순회 순서가 정렬 값이다.

중위 순회 순서: 1, 3, 5, 12, 24, 30, 49

 

트리 정렬 복잡도 분석

• 메모리 공간 사용
  • 원소 n개의 대하여 n개의 메모리 사용
  • 크기 n의 이진 탐색 트리 저장 공간
• 연산 시간
  • n개의 노드에 대한 시간 복잡도 O(nlog2 n)