트리 정렬은 이진 탐색 트리를 이용하여 정렬하는 방법이다.
정렬할 원소들을 이진 탐색 트리로 구성하고 중위 우선 순회 방법을
사용하여 이진 탐색 트리의 원소들을 순회하여 꺼내면 오름차순 정렬이 된다.
트리 정렬에서 원소들을 비교하여 이진 탐색 트리를 구성하는 시간이
O(log₂n) 이므로 n개의 노드에 대해서 이진 탐색 트리를 구성하는
시간 복잡도는 O(nlog₂n) 가 된다.
'프로그래밍 > 자료구조' 카테고리의 다른 글
[자료구조] 히프 정렬(heap sort)... (2) | 2011.11.03 |
---|---|
[자료구조]기수 정렬(radix sort).... (0) | 2011.11.02 |
[자료구조] 병합 정렬(merge sort).... (0) | 2011.11.02 |
[자료구조] 셸 정렬(shell sort)... (0) | 2011.10.31 |
[자료구조] 삽입 정렬(insert sort)... (0) | 2011.10.30 |