탐색(Search) - 순차, 이진, 보간, 이진 트리

탐색(Search) - 순차, 이진, 보간, 이진 트리

Algorithmday_4 정리 (2021.12.01 수요일)

탐색(Search)

데이터의 집단 내에서 특정 데이터를 찾는 구조

탐색 알고리즘의 효율성은 탐색 집단의 구조가 어떻게 구성되어 있느냐에 따라 영향을 받음

컴퓨터가 가장 많이 하는 작업 중 하나

탐색에 사용되는 자료 구조

배열, 연결 리스트, 트리, 그래프 등

탐색 방법

순차 탐색

이진 탐색

보간 탐색

이진 트리 탐색

순차 탐색(Sequential Search)

정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법

탐색 방법 중 가장 간단하고 직접적인 방법

크기가 적은 리스트에서는 효율적이지만 크기가 큰 리스트에서는 매우 비 효율적

장점 하나씩 비교하기 때문에 탐색 용이 탐색 알고리즘 간단

단점 탐색 시간이 느리며 수행 시간이 많이 걸림

9 5 8 3 7일 때 8을 찾는 경우 첫 인덱스부터 순차 탐색 하면 3번째에 찾음.

9 5 8 3 7일 때 2를 찾는 경우 첫 인덱스부터 순차 탐색 하면 탐색 실패.

이진 탐색(Binary Search)

전체 데이터 집합을 두 부분으로 나누어 검색하고자 하는 값이 어느 부분에 속하는 가를 결정하여 그 부분에 대하여 순환적으로 탐색을 수행하는 방법

정렬된 리스트에서 중간에 위치한 키 값과 찾고자 하는 값이 같으면 탐색 성공

탐색 실패 했을 때 다시 중간 항목을 기준으로 두 부분중 한쪽 리스트를 선택하여 키를 정한 후 다시 이진 탐색해서 찾으면 성공

그래도 없으면 다시 나머지 다른 한 쪽 이진 탐색

특징 분할 정복 기법에 의한 탐색 방법 중 하나 리스트가 정렬되어 있는 경우 적합한 탐색 방법 따라서 이진 탐색 방법을 적용할 경우 먼저 리스트 항목을 정렬시켜야 함 레코드 삽입, 삭제가 빈번하게 발생되는 경우 리스트 재구성을 위해 항목의 이동이 발생하기 때문에 삽입, 삭제가 거의 없는 리스트에 적합

5를 탐색.

[1, 3, 5, 6, 7, 9, 11, 20, 30] 중간 값을 키로 설정 (키 : 7)

[1, 3, 5, 6] 이 탐색 영역이 된다. (5가 7보다 작기 때문에)

[1, 3, 5, 6] 3을 키로 설정, 5와 비교

5가 3보다 크니 [5, 6]이 다시 탐색 영역

[5, 6] 5를 키로 설정 찾고자 하는 값은 5 탐색 완료

보간 탐색(Interpolation Search)

탐색하고자 하는 키 값의 위치를 예측하여 탐색하는 방법

사전이나 전화번호부를 탐색하는 방법과 동일 사전을 찾을 때 'ㅎ'으로 시작하는 단어는 사전의 뒷 부분에서 찾고 'ㄱ'으로 시작하는 단어는 앞 부분에서 찾는 것과 같은 원리

보간 탐색은 이진 탐색과 유사하지만 리스트를 반이 아닌 불균등하게 분할하여 탐색

리스트가 정렬되어 있는 경우 적합

많은 데이터가 균등하게 분포되어 있는 경우 보간 탐색이 이진 탐색보다 우수

이진 트리 탐색(Binary Tree Search)

탐색 속도와 항목을 효율적으로 수정할 수 있도록 주어진 리스트를 이진 트리로 구성하여 탐색하는 방법

root node를 중심으로 좌측 트리는 root node 보다 작은 값, 우측 트리는 큰 값이 존재하도록 구성

이진 탐색과 이진 트리 탐색의 차이점 근본적으로는 같은 원리 이진 탐색은 삽입, 삭제시에 앞뒤 원소를 이동시켜야 하지만 이진 트리 탐색에서는 비교적 빠른 시간안에 삽입 삭제 가능 삽입, 삭제가 빈번하다면 반드시 이진 트리 탐색 사용.

이진 탐색 트리에서 탐색 root node에서 시작 키 값 = root node 탐색 종료 키 값 > root node 오른쪽 서브트리만 탐색 키 값 < root node 왼쪽 서브트리만 탐색 탐색 성공하면 값 반환 결과가 공백이면 실패

이진 탐색 트리에서 삽입 키 값이 x인 원소를 삽입한다. x를 키 값으로 가지고 있는 원소가 있는지 탐색 탐색이 실패하면 탐색이 종료된 위치에 원소 삽입.

이진 탐색 트리에서의 삭제 삭제하려는 원소의 키 값이 주어졌을 때 이 키값을 가진 원소를 탐색 원소를 찾으면 삭제 연산 수행

해당 노드의 자식수에 따른 세가지 삭제 연산

자식이 없는 단말 노드의 삭제

제거할 노드가 단말 노드면 그대로 삭제

자식이 하나인 노드의 삭제

삭제되는 노드 자리에 그 자식 노드 트리를 위치

자식이 둘인 노드의 삭제

삭제되는 노드의 좌측 트리 중 제일 오른쪽 단말 노드로 대체

이진 탐색 트리 예제

Node.java

public class Node { int value; Node leftchild; Node rightchild; // 생성자 public Node(int value) { this.value = value; leftchild = null; // 객체이므로 null로 초기화 rightchild = null; } }

BinaryTree.java

public class BinaryTree { Node rootNode = null; public void insertNode(int element) { if(rootNode == null) { // 루트가 빈 경우 즉, 아무 노드도 없으면 노드 생성 rootNode = new Node(element); } else { Node head = rootNode; Node currentNode; while (true) { currentNode = head; // 현재 루트보다 작은 경우 왼쪽으로 탐색 if(head.value > element) { head = head.leftchild; // 왼쪽 자식 노드가 비어 있는 경우, 해당 위치에 추가할 노드 삽입 // 현재 currentNode는 head를 가리키고 있음 if(head == null) { currentNode.leftchild = new Node(element); break; } } else { // 현재 루트보다 큰 경우 오른쪽으로 탐색 head = head.rightchild; // 왼쪽 자식 노드가 비어 있는 경우, 해당 위치에 추가할 노드 삽입 // 현재 currentNode는 head를 가리키고 있음 if(head == null) { currentNode.rightchild = new Node(element); break; } } } } } // 전위 순회 root - left - right public void preorderTree(Node root, int depth) { if(root != null) { for(int i = 0; i < depth; i++) { System.out.print("ㄴ"); } System.out.println(root.value); // root preorderTree(root.leftchild, depth+1); // left preorderTree(root.rightchild, depth+1); // right } } // 중위 순회 left - root - right public void inorderTree(Node root, int depth) { if(root != null) { inorderTree(root.leftchild, depth+1); // left for(int i = 0; i < depth; i++) { System.out.print("ㄴ"); } System.out.println(root.value); // root inorderTree(root.rightchild, depth+1); // right } } // 중위 순회 left - right - root public void postorderTree(Node root, int depth) { if(root != null) { postorderTree(root.leftchild, depth+1); // left postorderTree(root.rightchild, depth+1); // right for(int i = 0; i < depth; i++) { System.out.print("ㄴ"); } System.out.println(root.value); // root } } public void searchBTree(Node n, int target) { try { if(target < n.value) { System.out.println("타겟이 " + n.value + "보다 작음"); searchBTree(n.leftchild, target); } else if(target > n.value) { System.out.println("타겟이 " + n.value + "보다 큼"); searchBTree(n.rightchild, target); } else { System.out.println("타겟이 " + n.value + "임"); } } catch (Exception e) { System.out.println("찾지 못함."); } } }

BinaryTreeMain.java

public class BinaryTreeMain { public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.insertNode(5); tree.insertNode(2); tree.insertNode(8); tree.insertNode(1); tree.insertNode(10); tree.insertNode(6); tree.insertNode(9); tree.insertNode(3); tree.insertNode(7); // 트리 운행(순회) tree.preorderTree(tree.rootNode, 0); System.out.println(); tree.inorderTree(tree.rootNode, 0); System.out.println(); tree.postorderTree(tree.rootNode, 0); System.out.println(); // 이진 트리 검색 tree.searchBTree(tree.rootNode, 10); } }

from http://5bong2-develop.tistory.com/63 by ccl(A) rewrite - 2021-12-01 15:26:49