Chapter07. 탐색

07-1 탐색이란?

탐색: 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업

레코드(record): 탐색을 위한 대상

테이블(table): 레코드의 집합

키(key) or 탐색키(search key): 여러 개의 필드로 이루어진 하나의 레코드에서 탐색의 기준이 되는 필드

 

탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업

 

테이블을 구성하는 방법에 따라 탐색의 효율이 달라짐

가장 간단한 방법인 배열을 사용하는 것보다는 탐색 트리나 해싱 같은 더 진보된 방법을 사용하는 것이 성능을 높일 수 있음

 

탐색 방법을 선택할 때 탐색 연산의 효율이 가장 중요하지만, 삽입, 삭제 연산과 같이 필요한 작업들을 함께 고려하여 알고리즘을 선택해야 함

 

---

07-2 순차 탐색

순차 탐색(sequential search), 선형 탐색(linear search)

일렬로 늘어선 자료(레코드) 중에서 원하는 킷값을 가진 레코드를 찾는 알고리즘

 

테이블은 배열이나 연결 리스트로 구성될 수 있음

 

순차 탐색은 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾음

 

순차 탐색 알고리즘

def sequential_search(A, key, low, high):
    for i in range(low, high+1):    # i: low, low+1, ... high
        if A[i] == key:             # 탐색 성공하면
            return i                # 인덱스 반환
    return -1                       # 탐색에 실패하면 -1 반환

탐색의 범위가 low에서 high까지라고 가정하여 리스트의 low 위치에서부터 순서대로 레코드를 탐색키와 비교

만약 같으면 그 레코드의 위치를 반환하고 high까지도 원하는 레코드가 나오지 않으면 실패이므로 -1 반환

 

순차 탐색의 빠르기

순차 탐색에서 가장 운이 좋은 경우는 찾는 자료가 맨 앞에 있는 경우로 1번의 비교만으로 탐색 완료

최악의 경우는 찾는 레코드가 테이블의 맨 뒤에 있거나 리스트에 없는 키를 찾는 경우

최악의 경우, 항상 모든 레코드를 탐색해야 하므로 탐색 범위만큼 비교 필요

 

테이블의 크기가 n일때 시간복잡도: O(n)

 

순차 탐색의 특징

• 탐색의 정의를 직접 사용하는 알고리즘으로 간단하고 구현하기 쉬움
• 효율적이지 않음. 최선의 경우 O(1)이고 최악이나 평균적인 경우가 O(n)인데 최선의 경우는 큰 의미 없음
• 테이블이 정렬되어 있지 않다면 순차 탐색 이외에 별다른 대안 없음 

 

순차 탐색을 개선하는 방법

자기 구성(self-organizing) 순차 탐색

탐색이 진행될때마다 자주 사용되는 레코드를 앞쪽으로 옮기는 방법으로 리스트를 재구성하여 탐색의 효율을 올림

이런 리스트를 자기 구성 리스트라고 함

 

리스트를 재구성하는 방법

- 맨 앞으로 보내기(move to front)

탐색에 성공한 레코드를 리스트의 맨 앞으로 보내는 방법

배열 구조의 경우 모든 레코드를 한 칸씩 뒤로 밀어야 하지만 연결된 구조에서는 효율적으로 처리 가능

한번 탐색된 레코드가 바로 이어서 다시 탐색될 가능성이 많은 응용에만 사용해야 함

 

- 교환하기(transpose)

탐색된 레코드를 바로 앞레코드와 교환

자주 탐색되는 레코드는 점진적으로 앞으로 이동하고, 그렇지 않은 레코드는 점진적으로 뒤로 밀리게 됨

 

교환하기 전략이 추가된 순차 탐색 알고리즘

def sequential_search_transpose(A, key, low, high):
    for i in range(low, high+1):
        if A[i] == key:
            if i > low:             # 맨 처음 요소가 아니면
                A[i], A[i-1] = A[i-1], A[i] # 교환하기(transpose)
                i = i-1             # 한 칸 앞으로 왔음
            return i                # 탐색에 성공하면 키 값의 인덱스 반환
    return -1                       # 탐색에 실패하면 -1 반환

 

이 외에도 레코드마다 탐색된 횟수를 별도의 공간에 각각 저장해두고, 탐색된 횟수가 많은 순으로 테이블을 재구성하는 전략(frequency count method)를 사용할 수 있음

이러한 방법들 모두 '지금까지 더 많이 탐색된 레코드가 앞으로도 더 많이 탐색될 가능성이 큰' 응용에만 적용되어야 함

 

 

---

07-3 이진 탐색

이진 탐색(binary search)

테이블이 킷값을 기준으로 정렬되어 있다면 한 번 비교할 때마다 탐색 범위가 절반으로 줄어드는 이진 탐색 알고리즘 사용 가능

 

테이블의 모든 레코드가 킷값의 오름차순으로 정렬되어 있다고 가정

이진 탐색은 먼저 테이블의 중앙에 있는 레코드를 탐색 키와 비교

• 중앙 레코드의 킷값이 탐색 키와 같으면 탐색 성공, 중앙 레코드의 위치(인덱스)를 반환
• 중앙 레코드가 탐색 키보다 크면 그보다 오른쪽에 잇는 모든 레코드는 탐색할 필요 없음
  왼쪽의 레코드들만 탐색하면 됨
• 중앙 레코드가 탐색 키보다 작으면 오른쪽만 탐색

이진 탐색에서는 단계마다 검색해야 할 레코드의 수가 반으로 줄어듦

 

찾는 값이 존재하지 않는 경우에는 결국 low와 high가 역전되면서 더 이상 검사해 볼 레코드가 없게 되어 탐색 실패가 됨

 

이진 탐색 알고리즘

이진 탐색 알고리즘(순환 구조)

def binary_search(A, key, low, high):
    if (low <= high):               # 항목들이 남아 있으면(종료 조건)
        middle = (low + high)//2    # middle 계산
        if key == A[middle]:        # 탐색 성공
            return middle           # 중앙 레코드의 인덱스 반환
        elif (key < A[middle]):     # 왼쪽 부분리스트 탐색 -> 순환호출
            return binary_search(A, key, low, middle-1)
        else:                       # 오른쪽 부분리스트 탐색 -> 순환호출
            return binary_search(A, key, middle+1, high)
    return -1                       # 탐색 실패 -1 반환

 

이진 탐색 알고리즘(반복 구조)

def binary_search_iter(A, key, low, high):
    while (low <= high):            # 항목들이 남아 있으면(종료 조건)
        middle = (low + high)//2    # middle 계산
        if key == A[middle]:        # 탐색 성공
            return middle
        elif (key > A[middle]):     # key가 middle의 값보다 크면
            low = middle + 1        # middle+1 ~ high 사이 검색
        else:                       # key가 middle의 값보다 작으면
            high = middle - 1       # low ~ middle-1 사이 검색
    return -1                       # 탐색 실패 -1 반환

 

 

이진 탐색의 빠르기

순환 호출을 한 번 할 때마다 탐색 범위가 다음과 같이 줄어듦

2^k → 2^(k-1) → 2^(k-2) → … → 2^1 → 2^0

단계의 수: k~0까지 k+1번

n=2^k 이므로 k = log2(n)

⇒ O(log2(n))

 

이진 탐색의 특징

• O(log2(n))의 매우 효율적인 탐색 방법
• 반드시 배열이 정렬되어 있어야 사용할 수 있음
• 테이블이 한 번 만들어지면 이후로 변경되지 않고 탐색 연산만 처리한다면 이진 탐색이 최고의 선택 중 하나

만약 테이블에 레코드를 삽입하거나 삭제하는 일이 빈번하게 일어나는 응용이라면 별로일 수 있음

삽입의 경우 크기가 n인 테이블에 새로운 레코드를 삽입하려면 삽입 후에도 테이블의 정렬 상태가 유지되어야 하므로 삽입이 정확한 위치에서 이루어져야 함 

→ 레코드가 들어가야 할 위치를 찾고 그 위치에 레코드를 끼워 넣을 때 테이블이 배열 구조라면 최악의 경우 이동해야 하는 레코드의 수는 n이 됨 ⇒ O(n)이 소요됨

 

테이블의 삽입이나 삭제가 빈번한 응용에는 이진 탐색이 좋지 않음

탐색은 효율적이나 비효율적인 삽입과 삭제 연산이 더 많이 처리되면 전체적으로는 불리할 수 있음

 

 

보간 탐색

보간 탐색(interpolation search): 이진 탐색의 일종으로 탐색 키가 존재할 위치를 예측하여 탐색하는 방법

 

보간 탐색에서는 탐색 범위 가장자리(low, high)에 있는 레코드의 킷값과 탐색 키의 비율을 고려하여 다음과 같이 탐색 위치를 계산

탐색위치 = low + (high - low) ⨉ (key - A[low]) / (A[high] - A[low])

 

보간 탐색은 레코드의 위치와 그 레코드의 킷값이 비례한다는 가정을 사용

탐색 위치를 결정할 때 탐색 키가 있는 곳에 좀 더 가중치를 줌

(A[high] - A[low]) : (key - A[low]) = (high - low) : (탐색위치 - low)

 

코드는 이진 탐색 함수에서 middle 계산만 다음과 같이 수정

middle = int(low + (high-low) * (key-A[low]) / (A[high]-A[low]))

 

보간 탐색은 이진 탐색과 같은 O(log2(n))의 시간 복잡도를 가짐

많은 데이터가 비교적 균등하게 분포된 자료의 경우 훨씬 효율적으로 사용될 수 있음

 

---

07-4 이진 탐색 트리

이진 탐색 트리(BST: Binary Search Tree)

효율적인 탐색을 위한 이진 트리

배열 구조의 테이블에서 이루어지는 이진 '탐색'의 성능은 유지하면서 '삽입'과 '삭제'도 효율적으로 처리

 

이진 탐색 트리의 조건

모든 노드가 '왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다'라는 규칙을 따름

이진 탐색 트리에서는 연산들을 보다 단순하게 설계하기 위해 보통 킷값의 중복을 허용하지 않음

 

이진 탐색 트리는 이진 트리의 한 종류이므로 공백검사, 순회, 노드의 수 등의 기본적인 연산을 그대로 사용할 수 있음

탐색, 삽입, 삭제같은 연산들은 반드시 이진 탐색 트리의 조건을 유지하면서 처리되어야 함

 

이진 탐색 트리의 탐색 연산

탐색은 항상 루트 노드에서 시작하여 아래로 내려감

탐색키의 값이 비교하는 노드보다 크면 오른쪽 자식으로 진행, 작으면 왼쪽으로 진행하며 탐색

 

 

노드 클래스 BSTNode

BTNode와 비슷하지만 데이터를 탐색을 위한 키(key)와 나머지 데이터 부분(value)으로 나누어 정의

 

이진 탐색 트리를 위한 노드 클래스

class BSTNode:                      # 이진 탐색 트리를 위한 노드 클래스               
    def __init__ (self, key, value):# 생성자: 키와 값을 받음
        self.key = key      # 키(key)
        self.value = value  # 값(value): 키를 제외한 데이터 부분
        self.left = None    # 왼쪽 자식에 대한 링크
        self.right = None   # 오른쪽 자식에 대한 링크

 

 

탐색 알고리즘: 키를 이용한 탐색

이진 탐색 트리의 탐색 연산(순환 구조)

def search_bst(n, key):
    if n == None:
        return None
    elif key == n.key:
        return n
    elif key < n.key:
        return search_bst(n.left, key)
    else:
        return search_bst(n.right, key)

 

탐색 알고리즘: 값을 이용한 탐색

이진 탐색 트리의 값을 이용한 탐색(전위 순회)

def search_value_bst(n, value):
    if n == None: return None
    elif value == n.value:
        return n
    res = search_value_bst(n.left, value)
    if res is not None:
        return res
    else:
        return search_value_bst(n.right, value)

 

 

이진 탐색 트리의 삽입 연산

삽입을 위해서는 탐색에 실패한 위치에 새로운 노드를 삽입해야 하기 때문에 먼저 삽입할 노드의 키를 이용한 탐색 과정을 수행해야 함

 

루트 노드를 시작으로 삽입하고자 하는 키 값을 갖는 노드를 탐색

탐색에 실패하면 해당 위치에 노드 삽입, 탐색에 성공하면 중복된 킷값을 가진 노드가 이미 있는 상태이므로 노드 삽입 X

 

이진 탐색 트리의 삽입 연산

def insert_bst(root, node): 
    if root == None:            # 공백 노드에 도달하면, 이 위치에 삽입
        return node             # node를 반환(이 노드가 현재 root 위치에 감)
    
    if node.key == root.key:    # 동일한 키는 허용하지 않음
        return root             # root를 반환(root는 변화 없음)
    
    # root의 서브 트리에 node 삽입
    if node.key < root.key:
        root.left = insert_bst(root.left, node)
    
    else:
        root.right = insert_bst(root.right, node)
    
    return root     # root를 반환(root는 변화 없음)

루트가 root인 노드에 새로운 노드 node를 삽입하는 연산을 순환 구조로 나타낸 알고리즘

 

삭제 연산

노드를 삭제한 후에도 이진 탐색 트리의 특생이 반드시 유지되어야 함

삭제할 노드의 자식 수에 따라 3가지 경우로 구분 됨

 

Case 1: 단말 노드의 삭제

삭제할 노드가 자식이 없는 단말 노드이면 그 노드만 없애면 됨

 

Case 2: 자식이 하나인 노드의 삭제

삭제할 노드가 하나의 자식을 갖는다면 그 자식을 부모 노드에 연결해주면 됨

 

Case 3: 2개의 자식을 모두 갖는 노드의 삭제

2개의 자식을 모두 갖는 노드의 경우 단순하게 해당 노드의 자식을 끌어올 경우 자식이 셋이 되므로 이진 트리의 조건을 불만족

 

적절한 노드(후계자)를 찾고, 후계자의 데이터를 삭제할 노드에 복사한 다음, 실제로는 후계자를 삭제

 

후계자로 적합한 후보 (킷 값이 최대한 비슷한 노드)

• 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 노드
• 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드

서브 트리에서 가장 큰 노드는 오른쪽 자식이 없어야 하고, 가장 작은 노드는 왼쪽 자식이 없어야 하므로 후계자 후보 노드는 1개 이하의 자식을 가짐

 

삭제 연산은 항상 삭제할 노드(root)를 대신할 노드가 반환됨

 

이진 탐색 트리의 삭제 연산

def delete_bst(root, key):
    if root == None:    # 공백 트리
        return root
    
    if key < root.key:
        root.left = delete_bst(root.left, key)
    elif key > root.key:
        root.right = delete_bst(root.right, key)

    # key가 루트의 키와 같으면 root를 삭제
    else:
        # case1(단말 노드) 또는 case2(오른쪽 자식만 있는 경우)
        if root.left == None:
            return root.right
        
        # case2(왼쪽 자식만 있는 경우)
        if root.right == None:
            return root.left
        
        # case3(두 자식이 모두 있는 경우):
        succ = root.right
        while succ.left != None:
            succ = succ.left

        root.key = succ.key
        root.value = succ.value
        root.right = delete_bst(root.right, succ.key)

    return root

순환 호출을 통해 찾고자 하는 킷 값을 가진 노드가 root가 되면 case에 따라 구분하여 해당 root를 대신할 노드를 반환하며 삭제됨

 

이진 탐색 트리의 성능

트리의 높이: h

전체 노드 수: n

• 최선의 경우
  이진 탐색 트리가 포화 이진 트리인 경우
  h = log2(n) 으로 가장 낮은 트리가 만들어지고, 탐색과 삽입, 삭제 연산이 모두 O(log2(n))에 처리됨
  
  
• 최악의 경우
  이진 탐색 트리가 한쪽으로 치우치는 경사 트리인 경우
  h = n 으로 트리의 높이와 노드의 수가 같아지면서 탐색 연산이 O(n)이 됨

이진 탐색 트리의 효율을 높이기 위해서는 트리가 좌우로 균형을 유지하도록 구성되어야 함

 

이진 탐색 트리의 테스트

이진 탐색 트리의 테스트 프로그램

def print_node(msg, n):
    print(msg, n if n != None else "탐색 실패")

def print_tree(msg, r):
    print(msg, end='')
    preorder(r)
    print()

data = [(6, "여섯"), (8, "여덟"), (2, "둘"), (4, "넷"), (7, "일곱"), 
        (5, "다섯"), (1, "하나"), (9, "아홉"), (3, "셋"), (0, "영")]

root = None                         # 루트 노드 초기화
for i in range(0, len(data)):       # 노드 순서대로 추가하기
    root = insert_bst(root, BSTNode(data[i][0], data[i][1]))

print_tree("최초: ", root)          # 최초의 트리 출력

n = search_bst(root, 3);    print_node("srch 3: ", n)
n = search_bst(root, 8);    print_node("srch 8: ", n)
n = search_bst(root, 0);    print_node("srch 0: ", n)
n = search_bst(root, 10);    print_node("srch 10: ", n)
n = search_value_bst(root, "둘");    print_node("srch 둘: ", n)
n = search_value_bst(root, "열");    print_node("srch 열: ", n)

root = delete_bst(root, 7);     print_tree("del 7: ", root)
root = delete_bst(root, 8);     print_tree("del 8: ", root)
root = delete_bst(root, 2);     print_tree("del 2: ", root)
root = delete_bst(root, 6);     print_tree("del 6: ", root)

 

이진 탐색 트리를 구축하기 위해 10개의 노드를 (숫자, 한글) 형태로, 숫자를 key 필드로 사용하여 삽입

이후에 탐색, 삭제 연산 수행하고 출력

 

실행 결과

최초: {(6:여섯){(2:둘){(1:하나){(0:영)}}{(4:넷){(3:셋)}{(5:다섯)}}}{{(8:여덟){(7:일곱)}{(9:아홉)}}}
srch 3: (3:셋)
srch 8: (8:여덟)
srch 0: (0:영)
srch 10: 탐색실패
srch 둘: (2:둘)
srch 열: 탐색실패
del 7: {(6:여섯){(2:둘){(1:하나){(0:영)}}{(4:넷){(3:셋)}{(5:다섯)}}}{(8:여덟)(9:아홉)}}}
del 8: {(6:여섯){(2:둘){(1:하나){(0:영)}}{(4:넷){(3:셋)}{(5:다섯)}}}{(9:아홉)}}
del 9: {(6:여섯){(3:셋){(1:하나){(0:영)}}{(4:넷){(5:다섯)}}}{(9:아홉)}}
del 6: {(9:아홉){(3:셋){(1:하나){(0:영)}}{(4:넷){(5:다섯)}}}}