탐색(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);
    }
}