[Coding Interview University] 이진탐색 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 트리

: 하나의 루트 코드를 가진다

: 루트 노드는 0개 이상의 자식 노드를 갖고 있다

: 트리에는 사이클 존재할 수 없다

: 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다

: 각 노드는 어떤 자료형으로도 표현이 가능하다

 

🫧 이진트리

: 각 노드가 최대 두 개의 자식을 갖는 트리

 

🫧 이진탐색트리

: “모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들” 속성은 모든 노드 n에 대해서 반드시 참이어야 함

: 모든 노드에 대해서 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들 값은 현재 노드의 값보다 반드시 커야함

 

🫧 균형 vs 비균형

• 균형
  • 레드 블랙 트리
  • AVL 트리

 

🫧 완전이진트리

: 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리

: 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

 

🫧 전이진트리

: 모든 노드의 자식이 없거나 정확히 두 개 있는 경우

: 자식이 하나만 있는 노드가 존재해서는 안됨

 

🫧 포화이진트리

: 전 이진 트리이면서 완전 이진 트리인 경우

: 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다

: 노드의 개수가 정확히 2^K-1 (K는 트리의 높이) 개

 

🫧 이진 탐색

처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문

 

🫧 (정수가 정렬된 배열에서) 이진 탐색

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

 

🫧 재귀를 사용한 이진 탐색

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}