etc./알고리즘
검색 알고리즘(이진탐색)
okbear3
2022. 3. 23. 14:50
검색 알고리즘
1. 선형검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
검색 외에도 데이터 삽입 및 삭제 작업에서 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야한다.
선택한 알고리즘의 용도나 목적, 실행속도, 자료구조 등을 고려하여 알고리즘을 선택
순차 탐색(sequential search)
- 검색 대상의 자료를 처음부터 하나씩 비교하여 검색한다.
- 검색 대상 자료가 순서적으로 정렬되어 있지 않아도 검색이 가능하다.
- 검색 대상 자료들의 수를 알지 못할 때 사용한다.
- 단순하고 검색 속도가 느림으로 자료가 적을 때 유리하다.
- 검색 대상이 배열에 없을 경우 최악의 경우로 n번 검색한다.
- 시간 복잡도
- worst case : O(n) -> 검색에 실패한 경우
- Average case : O((n+1)/2)
static int seqSearch(int[] a, int n, int key){
for(int i=0;i<n;i++)
if(a[i]==key) return i; //검색 성공
return -1; //검색 실패
}이진 탐색(binary search)
- 검색 대상의 전체 자료를 이등분 하면서 검색하는 방법이다.
- 이진 탐색을 하려면 검색 대상의 전체 자료의 수를 알고 있어야 한다.
- 이진 탐색을 하려면 검색 대상의 자료들이 정렬 되어있어야 한다.
- 시간 복잡도
- worst case : O(log n)+1 -> 검색에 실패한 경우
- Average case : O(log n) -> 검색 범위를 반씩 좁혀나감
static int binarysearch(int[] a, int key){
Arrays.sort(a); //이진 탐색은 정렬된 상태에서 시작
int left = 0;
int right = a.length()-1; //최악의 경우
while(left>=right){
int mid = (left+right)/2; //중간값 mid
if(mid>key)left = mid+1; //배열의 왼쪽 탐색
else if(mid<key) right = mid-1; //배열의 오른쪽 탐색
else return mid; //mid == key
}
return -1;
}java.util.Arrays 클래스에는 binarySearch 메서드가 있다.
binarySearch 메서드는 오름차순으로 정렬된 배열을 가정하고, 키 값이 key인 요소를 이진검색한다.
binarySearch 메서드는 자료형에 따라 9가지 방법으로 오버로딩 되어 있습니다.
검색에 성공한 경우
- 일치하는 요소의 인덱스를 반환
- 일치하는 요소가 여러개 있다면 무작위로 인덱스를 반환
검색에 실패한 경우
- 삽입 포인트를 x라고 할 때 -x-1을 반환(음수의 숫자를 반환)static int BS(int[] x, int key){
Arrays.sort(x); //binarySearch 전에 배열 정렬
int idx = Arrays.binarySearch(x,key); //배열 x에서 키 값이 key인 요소를 검색
}이진 트리 검색(Binary Tree Search)
- 검색 대상의 자료를 이진 트리로 변형한 뒤 검색하는 방법
- 처음의 자료는 근노드가 되고, 두번째 자료는 근노드와 비교해서 작으면 왼쪽으로, 크면 오른쪽에 연결한다.
- 모두 연결된 이진 트리를 근 노드에 있는 값을 비교하여 찾고자 하는 값에 따라 왼쪽 또는 오른쪽을 다시 비교한다.
- 비어있지 않다면 모든 노드(node)는 서로 다른 값(key)을 갖습니다.
- 시간 복잡도
- O(log n)
다음의 코드는 이진트리의 삽입과 삭제 검색을 구현한 알고리즘이다.
package algorithm.Search;
import java.util.Comparator;
public class BinTree <K,V>{
//노드
static class Node<K,V>{
private K key; //키 값
private V data; //데이터
private Node<K,V> left; //왼쪽 자식 노드
private Node<K,V> right; //오른쪽 자식 노드
//생성자
Node(K key,V data, Node<K,V> left, Node<K,V> right){
this.key = key;
this.data = data;
this.left = left;
this.right = right;
}
K getKey(){ return key;}
V getValue(){ return data;}
void print(){ System.out.println(data);}
}
private Node<K,V> root; //루트(첫번째 노드)
private Comparator<? super K> comparator = null; //비교자
//노드가 하나도 없는 트리 생성
public BinTree(){ root = null;} //자연 순서로 키 값을 비교
//인수로 비교자를 전달받는 생성자
public BinTree(Comparator<? super K> c){ //비교자로 키 비교
this(); //this()에 의해 인수를 전달받지 않는 생성자 BinTree를 호출(root = null 인 이진검색 트리 생성)
comparator = c; //필드 comparator에 전달받은 c를 설정
}
//두 키 값을 비교하는 comp 메서드
private int comp(K key1, K key2){
return (comparator==null) ? ((Comparable<K>)key1).compareTo(key2) : comparator.compare(key1,key2);
//key1>key2 =>양수
//key1<key2 =>음수
//key1==key2 => 0
}
//이진검색트리에서 노드를 검색
public V search(K key){
Node<K,V> p = root;
while(true){
if(p==null) return null; //더이상 진행하지 않으면 검색 실패
int cond = comp(key,p.getKey()); //key와 노드 p의 키를 비교
if(cond==0) return p.getValue(); //같으면 검색 성공 => 노드의 데이터에 대한 참조를 반환
else if(cond<0) p=p.left; //key 쪽이 더 작으면 왼쪽 서브트리에서 검색
else p=p.right; //key 쪽이 더 크면 오른쪽 서브트리에서 검색
}
}
//node를 루트로 하는 서브트리에 노드<K,V>를 삽입
private void addNode(Node<K,V> node, K key, V data){
int cond = comp(key,node.getKey());
if(cond==0)return; //삽입 과정에서 key가 이미 이진 트리에 있음
else if(cond<0){ //왼쪽 서브트리
if(node.left==null) node.left = new Node<K,V>(key,data,null,null); //서브트리가 비어있으면 노드 생성
else addNode(node.left, key,data); //왼쪽 노드 탐색
}
else{ //오른쪽 서브트리
if(node.right==null) node.right = new Node<K,V>(key,data,null,null);
else addNode(node.right,key,data); //오른쪽 노드 탐색
}
}
public void add(K key, V data){
if(root==null) root = new Node(key,data,null,null); //트리가 비어있는 상태이므로 첫번째 루트 생성
else addNode(root,key,data); //addNode를 호출하여 노드를 삽입
}
//Node를 삭제하는 remove 메서드
public boolean remove(K key){
Node<K,V> p = root;
Node<K,V> parent = null;
boolean isLeftChild = true;
//1. 자식 노드가 없는 노드를 삭제하는 경우
while(true){
if(p==null) return false; //더이상 진행하지 않으면 키 값이 없음
int cond = comp(key,p.getKey());
if(cond==0) break; //key와 노드 p의 키 값을 비교해서 같으면 검색 성공
else{
parent = p; //가지로 내려가기 전에 부모를 설정
if(cond<0){
isLeftChild = true;
p = p.left; //왼쪽 서브트리에서 검색
}
else{
isLeftChild = false; //key쪽이 크면 오른쪽 자식으로 내려감
p = p.right; //오른쪽 서브트리에서 검색
}
}
}
//2. 자식 노드가 1개인 노드를 삭제하는 경우
if(p.left==null){ //p에 왼쪽 자식이 없을 때
if(p==root) root = p.right;
else if(isLeftChild) parent.left = p.right; //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
else parent.right = p.right; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
}
else if(p.right==null){ //p에 오른쪽 자식이 없을 때
if(p==root) root = p.left;
else if(isLeftChild) parent.left = p.left; //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
else parent.right = p.left; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
}
//3. 자식 노드가 2개인 노드를 삭제하는 경우
else{
parent = p;
Node<K,V> left = p.left; //서브 트리 가운데 가장 큰 노드
isLeftChild = true;
while(left.right!=null){ //가장 큰 노드 left를 검색
parent = left;
left = left.right;
isLeftChild = false;
}
p.key = left.key; //left의 key와 data를 p로 옮김
p.data = left.data;
if(isLeftChild) parent.left = left.left; //left를 삭제
else parent.right = left.left; //left를 삭제
}
return true;
}
//모든 노드를 출력하는 print 메서드
//inorder 방법으로 트리를 검색하는 방법
private void printSubTree(Node node){
if(node!=null){
printSubTree(node.left); //왼쪽 서브 트리를 키 값의 오름차순으로 출력
System.out.println(node.key+" "+node.data); //해당 node를 출력
printSubTree(node.right); //오른쪽 서브 트리를 키 값의 오름차순으로 출력
}
}
//모든 노드를 키 값의 오름차순으로 출력
public void print(){
printSubTree(root);
}
}