[Algorithm] Binary Search (이분 탐색) 개념

📌이분 탐색(바이너리 서치)이란?

• 각 노드에 값이 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

📌이분 탐색의 검색 (Search)

• **조건 : 미리 정렬되어 있어야 한다.
• 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.
• 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.
  • 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
  • 불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.
• 시간 복잡도 : O(longN)
• 수도코드 : 재귀함수

BinarySearch(A[], value, left, right) {
  if (right <= left)
    return -1 
  mid = (left + right) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, left, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, right)
  else
    return mid 
}

• 수도코드 : 반복문

 while (left <= right){
        mid = (left + right) / 2;
        if(target == mid)
        	return mid;
        else if (A[mid] > target)
            right = mid - 1;
        else if (A[mid] < target)
            left = mid + 1;
    }

 

📌이분 탐색의 삽입 (Insert)

• 삽입을 하기 전, 검색을 수행한다.
• 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

📌이분 탐색의 삭제 (Delete)

삭제하려는 노드의 자식 수에 따라

• 자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
• 자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
• 자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

---

💡참고

ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

이진 탐색 트리 - 위키백과, 우리 모두의 백과사전