728x90
- 트리 정렬(Tree Sort)이란?
이진 탐색 트리를 만들어 정렬하는 방식. 힙 정렬과 비슷해 보이지만 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 자식이 되느냐 오른쪽 자식이 되느냐가 다르다.
- 트리 정렬의 정렬 과정
-
정렬될 배열의 맨 첫 값이 루트 노드가 된다.
-
다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다.
-
위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 방향의 자식 노드가 있으면 계속 그 방향으로 가서 조사하고 없으면 그 방향의 자식 노드로 추가한다.
-
모든 값이 노드로 추가되었으면 해당 트리를 중위 순회 방식으로 순회하여 그 순서대로 값을 정렬해 나간다.
예를 들어, [4, 6, 1, 7, 5, 8, 2, 3]을 트리 정렬로 정렬하기 위해 이진 트리를 만들면 아래와 같이 된다.
이 이진 트리를 중위 순회 방식(왼쪽 자식 - 자신 - 오른쪽 자식 순)으로 순회하면(위 그림에서 무지개색 순으로 순회한다) [1, 2, 3, 4, 5, 6, 7, 8]이 된다.
728x90