이진 트리 검색(Binary Tree Search)

이진 트리 검색(Binary Tree Search)

루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키 값이 작은 원소들로, 오른쪽 서브 트리는 루트 노드보다 키 값이 큰 원소들로 구성된 '이진 탐색 트리'를 사용하여 중위 순회 방법으로 검색.

삽입, 삭제 연산 후에는 항상 이진 탐색 트리를 재구성해야 한다.

예시 1) 20를 찾는 경우

4 17

/\ /\

1 7 14 20

1. 루트 노드에서 검색을 시작하여 키 값과 비교한다. 키 값이 루트 노드보다 크기 때문에 오른쪽 노드로 이동한다.

4 17

/\ /\

1 7 14 20

2. 이동한 오른쪽 노드와 키 값을 비교한다. 키 값이 17보다 크기 때문에 오른쪽 노드로 이동한다.

4 17

/\ /\

1 7 14 20

3. 이동한 오른쪽 노드와 키 값을 비교한다. 키 값과 일치하기 때문에 검색을 종료한다..

4 17

/\ /\

1 7 14 20

예시 2) 6을 찾는 경우

4 17

/\ /\

1 7 14 20

1. 루트 노드에서 검색을 시작하여 키 값과 비교한다. 키 값이 루트 노드보다 작기 때문에 왼쪽 노드로 이동한다.

4 17

/\ /\

1 7 14 20

2. 이동한 왼쪽 노드와 키 값을 비교한다. 키 값이 4보다 크기 때문에 오른쪽 노드로 이동한다.

4 17

/\ /\

1 7 14 20

3. 이동한 오른쪽 노드와 키 값을 비교한다. 키 값과 일치하지 않기 때문에 검색 실패로 검색을 종료한다.

프로그램 작성)

package test;

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

class BinarySearchTree {
	public 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);
	}
	
	public void search(TreeNode current, int key) {
		if(current == null) {
			System.out.println("찾는 값 없음.");
		} else if(current.data > key) {
			System.out.println("현재 값 : " + current.data + " > " + key);
			search(current.left, key);
		} else if(current.data < key) {
			System.out.println("현재 값 : " + current.data + " < " + key);
			search(current.right, key);
		} else {
			System.out.printf("찾은 값 : %d", key);
		}
	}
}

class Search {
	BinarySearchTree bst = new BinarySearchTree();
	public void binaryTreeSearch(int[] a, int key) {
		for(int i=0; i<a.length; i++) {
			bst.insertBST(a[i]);
		}
		
		bst.search(bst.root, key);
	}
}

public class Test {
	public static void main(String[] args) {
		int[] a = {9, 4, 17, 14, 20, 1, 7};

		System.out.println("배열 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();
		System.out.println();

		Search s = new Search();
		s.binaryTreeSearch(a, 20);
		System.out.println();
		System.out.println();

		s.binaryTreeSearch(a, 6);
		System.out.println();
	}
}

실행 결과)