[F-Lab 모각코 챌린지 22일차] Binary Search Tree, thread

TIL

1. 이진 탐색
   • 알고리즘
   • 이진 탐색 트리 개념
   • 이진 탐색 트리 삽입/검색/삭제 구현
   • 이진 탐색 트리 평가
2. thread
   • 프로세스와 스레드의 특징
   • 스레드 구현
     
     

---

 

이진 탐색

이진 탐색 알고리즘

• 범위를 반으로 줄여가며 탐색하는 것
• 예를 들어, up & down 게임을 한다고 하자.
  1~50까지 숫자 중에 하나를 고르고(3) 범위를 반 씩 줄여나가며 3을 찾아낸다.
  1. 1 ~ 50의 반절인 25를 부르면 down (정답이 1~24까지로 범위가 좁혀진다.)
  2. 1 ~ 24의 반절인 12를 부르면 down (정답이 1~11까지로 범위가 좁혀진다.)
  3. 1 ~ 11의 약 반절 값인 6을 부르면 down (정답이 1~5까지로 범위가 좁혀진다.)
  4. 1 ~ 5의 약 반절 값인 3을 부르면 정답!

 

만약 50을 찾아내야 된다고 해도 이진 탐색 알고리즘을 사용하면 6번만에 찾아낼 수 있다.

매 선택마다 범위가 반으로 줄어들기 때문에 log₂50 즉, 5.6으로 6번 이하의 시도로 해당 값을 찾아낸다.
최악의 경우에 6번 시도를 하여 해당 값을 찾아내므로 O(logN) 성능을 갖는다.

 

하지만 이진 탐색에는 단점이 있다. 데이터가 정렬돼있어야 한다는 것이다.
위 예제만 봐도 1 ~ 50까지의 숫자들이 차례대로 정렬되어있지 않다면 이진 탐색을 하는 의미가 없다.
(* 이진 탐색 트리는 이진 탐색 알고리즘의 장점은 취하고 단점은 뺀 자료구조이다.)

 

 

 

 

이진 탐색 알고리즘 구현

코드랑 그림 짚어가면서 보기

 

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Main main = new Main();
    int index = main.binarySearch(arr, 3, 0, arr.length - 1);
    System.out.println("target index: " + index); // 2
}

/**
 * Binary Search
 * @param arr    정렬된 배열
 * @param target 찾는 값
 * @param start  배열의 start index
 * @param end    배열의 end index
 * @return       찾은 값의 index
 */
public int binarySearch(int[] arr, int target, int start, int end) {
    // 배열을 반으로 쪼개다가 더 이상 쪼갤 것이 없을 때, 메소드 종료
    if (start > end) {
        return -1;
    }

    int mid = (start + end) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (target > arr[mid]) {
        return binarySearch(arr, target, mid + 1, end);
    } else {
        return binarySearch(arr, target, start, mid - 1);
    }

}

 

 

 

 

이진 탐색 트리

이진 탐색 알고리즘의 단점에 대해 다시 한 번 살펴보자.

1. 배열이 정렬돼 있어야한다.
2. 배열은 데이터의 삽입/삭제에 많은 비용이 든다.

 

사용자가 데이터의 삽입과 삭제를 자주 하면서 탐색도 자주 한다고 하면 어떤 자료구조가 알맞을까?
바로 해시테이블이다.
해시테이블은 해시함수의 질만 좋다면 데이터의 삽입, 삭제가 빠르고 검색은 O(1) 성능으로 매우 빠르다.

 

하지만 해시테이블도 단점이 있다.

1. 해시함수를 대충 만들어 해시충돌이 잦아지면 성능이 급격히 안 좋아진다.
2. 데이터가 정렬돼 있지 않고, 테이블을 만들어 놓아야하기 때문에 메모리도 더 많이 필요하다.

 

이진 탐색 트리는 해시테이블처럼 잦은 데이터 삽입, 삭제 그리고 검색에도 빠른 성능을 보인다.
데이터는 정렬하여 저장하고 해시테이블보다 메모리 사용량도 적다.

 

 

 

 

이진 탐색 트리가 되기 위한 규칙

1. 트리를 이루는 노드들은 중복된 값을 가질 수 없다.
   즉, 5를 갖고 있는 노드가 있다면 해당 트리에선 더 이상 5를 추가할 수 없다.

 

2. 특정 노드의 왼쪽 자식노드는 그 특정 노드의 값보다 작은 값으로만 이루어진다.
3. 특정 노드의 오른쪽 자식노드는 그 특정 노드의 값보다 큰 값으로만 이루어진다.
4. 모든 서브트리에도 위의 규칙이 적용되어야 한다.

 

이진 탐색 트리의 대표적인 기능은 데이터 삽입/삭제/탐색이다.
이진 탐색 트리에서 데이터를 삭제하는 건 좀 복잡하다.

 

 

 

 

이진 탐색 트리 삽입/탐색 구현

• 이진 탐색 트리의 데이터 삽입과 탐색은 루트노드부터 시작해 null을 만날 때까지 비교하면서 좌우로 내려가는 작업이다.
  
  

코드랑 그림 짚어가면서 보기

 

public static void main(String[] args) {

    BinarySearchTree tree = new BinarySearchTree();
    tree.insert(18);
    tree.insert(15);
    tree.insert(10);
    tree.insert(6);
    tree.insert(3);
    tree.insert(8);
    tree.insert(12);
    tree.insert(11);
    tree.insert(31);
    tree.insert(27);
    tree.insert(24);
    tree.insert(20);
    tree.insert(33);
    tree.insert(35);
    tree.insert(37);

    // 중위순회로 모든 노드 출력
    // 3 6 8 10 11 12 15 18 20 24 27 31 33 35 37
    tree.root.inOrderTraversal(tree.root);

    // 특정 데이터를 가지고 있는 노드 탐색
    BinaryTree targetNode1 = tree.search(6);
    BinaryTree targetNode2 = tree.search(1); // null
}

public class BinarySearchTree {
    BinaryTree root = null;

	// 데이터 삽입
    public void insert(int data) {
        // 이진탐색트리에 노드가 하나도 없을 때, 데이터 삽입
        if (this.root == null) {
            this.root = new BinaryTree(data);
            return;
        }

        // 이진탐색트리에 데이터가 1개 이상 있는 경우
        BinaryTree currentNode = this.root;
        BinaryTree parentNode = null; // 삽입할 데이터를 부모노드와 연결해주기 위해 부모노드를 참조해야 한다.

        while (currentNode != null) {
            parentNode = currentNode;

            if (data < currentNode.getData()) {
                currentNode = currentNode.getLeftSubTree();
            } else if (data > currentNode.getData()) {
                currentNode = currentNode.getRightSubTree();
            } else { // 값의 중복을 허용하지 않기 때문에 메소드 종료
                return;
            }
        }

        BinaryTree newNode = new BinaryTree(data);

        if (data < parentNode.getData()) {
            parentNode.setLeftSubTree(newNode);
        } else {
            parentNode.setRightSubTree(newNode);
        }
    }

	// 데이터 탐색
    public BinaryTree search(int targetData) {
        BinaryTree currentNode = root;

        while (currentNode != null) {
            if (currentNode.getData() == targetData) {
                return currentNode;
            } else if (currentNode.getData() > targetData) {
                currentNode = currentNode.getLeftSubTree();
            } else {
                currentNode = currentNode.getRightSubTree();
            }
        }

        return null;
    }
}

public class BinaryTree {
    private int data;
    private BinaryTree leftSubTree;
    private BinaryTree rightSubTree;

    BinaryTree(int data) {
        this.data = data;
    }

    // 중위순회 출력
    public void inOrderTraversal(BinaryTree tree) {
        if (tree == null) {
            return;
        }

        this.inOrderTraversal(tree.getLeftSubTree());
        System.out.println(tree.data);
        this.inOrderTraversal(tree.getRightSubTree());
    }

    // 다른 메소드 생략
}

 

 

 

 

thread

프로세스란

• 실행 중인 프로그램
• 자원(메모리, CPU 등)과 스레드로 구성
• 비유하자면 공장(작업환경)

 

 

 

스레드

• 프로세스 내에서 실제로 작업을 수행하는 주체
• 모든 프로세스는 최소한 1개 이상의 스레드를 가지고 있다.
• 비유하자면 일꾼
• 싱글스레드 프로세스 = 자원 + 1개의 스레드
• 멀티스레드 프로세스 = 자원 + 여러 개의 스레드

 

하나의 새로운 프로세스를 생성하는 것보다,
하나의 새로운 스레드를 생성하는 것이 더 적은 비용이 든다.

 

ex) CGI vs Java Servelt

• CGI는 사용자로부터 요청이 올 때마다 프로세스를 하나씩 만든다. (싱글스레드)

 

 

 

• Java Servlet은 멀티스레드를 지원한다.
• 따라서, 사용자로부터 요청이 올 때마다 스레드를 하나씩 만든다. (멀티스레드)
• CGI 방식과 비교했을 때, 한 대의 웹서버를 가지고 더 많은 사용자의 요청을 처리할 수 있다.

 

 

 

 

멀티스레드의 특징

• 대부분의 프로그램은 멀티스레드로 작성되어 있다.
• 장점
  • 시스템 자원을 효율적으로 사용할 수 있다.
  • 사용자에 대한 응답성이 향상 된다.
    ex) 친구랑 카톡하다가 내가 파일을 전송 했는데 파일 전송을 마칠 때까지 채팅 안 된다면? 멀티스레드 방식으로 프로그램을 작성하면 이런 일이 발생하지 않는다.
  • 각 스레드별로 나눠서 코드를 작성하기 때문에 코드가 간결해진다.
    
    
• 단점 (대부분 자원을 공유하는데서 문제가 발생)
  • 동기화에 주의해야 한다.
  • 교착상태(dead-lock, 서로 대치)가 발생하지 않도록 주의해야 한다.
  • 각 스레드가 효율적으로 고르게 실행될 수 있게 해야 한다.
  • 기아 가능성(특정 스레드는 작업할 기회를 갖지 못하고 작업 진행이 안 되는 것)
  • 프로그래밍할 때, 고려해야 할 사항들이 많다.

 

 

 

 

스레드 구현하는 방법

1. Thread 클래스를 상속
2. Runnable 인터페이스를 구현 (권장)

 

public static void main(String[] args) {
    Thread1 t1 = new Thread1();

    Runnable r  = new Thread2();
    Thread t2 = new Thread(r); // Thread(Runnable target) 생성자

    // Thread t1, t2 2개를 만들고 각 스레드를 따로 돌림
    t1.start();
    t2.start();
}

class Thread1 extends Thread { // Thread 클래스를 상속해서 스레드 구현
    public void run() { // 스레드가 수행할 작업
        for (int i = 0; i < 5; i++) {
            System.out.println(getName()); // 조상 Thread의 getName()메소드 호출
        }
    }
}

class Thread2 implements Runnable { // Runnable 인터페이스를 구현하여 스레드 구현
    @Override
    public void run() { // 스레드가 수행할 작업
        for (int i = 0; i < 5; i++) {
            // 현재 실행 중인 Thread 반환
            System.out.println(Thread.currentThread().getName());
        }
    }
}

 

 

 

 

스레드의 실행 start()


• 스레드를 생성한 후, start() 메소드를 호출해야 스레드가 작업을 시작한다.

 

Thread1 t1 = new Thread1(); // 스레드 생성
Thread2 t2 = new Thread2(); // 스레드 생성

t1.start(); // 스레드 작업 시작
t2.start(); // 스레드 작업 시작

• start() 했다고 스레드가 바로 실행되는 것은 아니다. 또한, t1과 t2 중 어떤 스레드가 먼저 시작될 지도 모른다. 스레드를 start() 하면 실행 가능한 상태가 되는 거지, 바로 시작!!! 할 수 있는 건 아니다.
• 스레드가 언제 시작될 지는 OS의 스케줄러가 결정한다. (스레드는 OS에 의존적인 면을 가지고 있다.)

 

• 그런데 작성한 메소드는 run() 메소드인데 왜 스레드 실행을 위해 start() 메소드를 호출할까?

main() 메소드 위에 그냥 run() 메소드를 올리게 되면 그냥 하나의 호출스택을 하나의 스레드가 실행하는 것이다.
반드시 start() 메소드를 호출해야 새로운 호출스택이 생성되고 그 곳에 run()이 올라가 각각의 스레드로 활동할 수가 있다.

 

 

 

 

 

📚 참고
자바의 정석
그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)