정렬 / ①

문제 13) 트리정렬(Tree Sort)

답)

 

1. O(log2N)의 시간 복잡도, 트리정렬(Tree Sort)의 개요

가. 트리정렬(Tree Sort)의 정의

• 이진 탐색 트리 형태의 구성을 띄면서 데이터가 삽입/삭제될 경우 트리탐색 과정을 거쳐 재구성한 후, 키 값을 삽입 후 중위 순회를 수행하는 정렬 알고리즘

 

나. 이진 탐색 트리 원리

	(규칙1) 모든 원소의 키는 유일해야 함
	(규칙1) 루트보다 작은 값은 왼쪽에 위치
	(규칙1) 루트보다 큰 값은 오른쪽에 위치
이진 탐색 트리로 삽입된 1, 3, 6, 8, 10 값을 중위순회 방법으로 오름차순 정렬 진행함

 

2. 트리정렬(Tree Sort) 매커니즘

 

개념도	순서	매커니즘 설명
	1	정렬할 원소N개를 차레대로 트리에 삽입하여 이진 탐색 트리 구성 [8, 3, 10, 1, 6]
	2	이진 탐색 트리를 중위 순회 방법으로 순회하면서 원소 저장 [1, 3, 6, 8, 10] (오름차순)
코드 사례는 다음과 같음

 

3. 트리정렬(Tree Sort) 코드

코드 예시

class Node { public: int key; Node *left, *right; }; Node* newNode(int item) { Node *temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp; } void inorder(Node *root, int arr[], int &i) { if (root != NULL) { inorder(root->left, arr, i); arr[i++] = root->key; inorder(root->right, arr, i); } } Node* insertintoBST(Node* node, int key) { if (node == NULL) return newNode(key); if (key < node->key) node->left = insertintoBST(node->left, key); else if (key > node->key) node->right = insertintoBST(node->right, key); return node; } void treeSort(int arr[], int n) { Node *root = NULL; root = insertintoBST(root, arr[0]); for (int i = 1; i < n; i++) root = insertintoBST(root, arr[i]); int i = 0; inorder(root, arr, i); }

 

 

---

 

공감과 댓글은 아이티신비에게 큰 힘이 됩니다.

블로그 글이 유용하다면 블로그를 구독해주세요.♥