트리 정렬(Tree Sort)

트리 정렬(Tree Sort)

정렬되지 않은 원소들을 이진 탐색 트리(왼쪽 자식 노드에는 자신보다 작은, 오른쪽 자식 노드에는 자신보다 큰 값인 이진 트리)로 구성한 후 중위 순회 방법(현재 노드의 왼쪽 서브 트리로 이동 -> 현재 노드 -> 현재 노드의 오른쪽 서브 트리로 이동)으로 순회하면서 오름차순으로 정렬한다.

​

시간 복잡도는 O(nlog2n)이다.

​

예시)

{57, 16, 41, 2, 50, 6, 32, 27}

​

1. 이진 탐색 트리로 구성

                            57

                           /

                        27

                        /\

                   6       41

                   /\.      /\

                 2 16  32 50

 

2. 중위 순회 방법으로 오름차순 정렬

{2, 6, 16, 27, 32, 41, 50, 57}

​

프로그램 작성)

package test;

class TreeNode {
	int data;
	TreeNode left;
	TreeNode right;
}

class BinarySearchTree {
	private TreeNode root = null;
	
	public TreeNode insertKey(TreeNode root, int x) {
		TreeNode p = root;
		TreeNode newNode = new TreeNode();
		newNode.data = x;
		newNode.left = null;
		newNode.right = null;
		
		if(p == null) {
			return newNode;
		} else if(newNode.data < p.data) {
			p.left = insertKey(p.left, x);
			return p;
		} else if(newNode.data > p.data) {
			p.right = insertKey(p.right, x);
			return p;
		} else {
			return p;
		}
	}
	
	public void insertBST(int x) {
		root = insertKey(root, x);
	}
	
	public void inorder(TreeNode root) {
		if(root != null) {
			inorder(root.left);
			System.out.print(" " + root.data);
			inorder(root.right);
		}
	}
	
	public void printBST() {
		System.out.println("중위 순회 : ");
		inorder(root);
	}
}

class Sort {
	BinarySearchTree bst = new BinarySearchTree();
	
	public void treeSort(int[] a) {
		for(int i=0; i<a.length; i++) {
			bst.insertBST(a[i]);
		}
			
		bst.printBST();
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.treeSort(a);
	}
}

실행 결과)