자료구조와 알고리즘 with 파이썬 chapter07. 탐색

07-1 탐색이란?

• 탐색 : 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업. 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업. 
• 레코드 : 탐색을 위한 대상
• 테이블 : 레코드의 집합
• 키 : 탐색의 기준에 되는 필드(탐색키)

07-2 순차탐색

• 순차 탐색 : 일렬로 늘어선 자료중에서 원하는 킷값을 가진 레코드를 찾는 알고리즘. 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾는다. 레코드들이 무질서하게 섞여 있어도 항상 원하는 레코드를 찾을 수 있다. 

def sequential_search(A, key, low, high):
	for i in range(low, high+1):
    	if A[i] == key:
        	return i
    return -1

순차 탐색은 얼마나 빠를까요?

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

순차 탐색을 개선하는 방법은?

• 자기 구성 순차 탐색 : 탐색이 진행될 때마다 자주 사용되는 레코드를 앞쪽으로 옮기는 방법. 리스트를 재구성하여 탐색의 효율을 끌어올린다. 이런 리스트를 자기 구성 리스트라고 한다. 
  • 맨 앞으로 보내기 : 탐색에 성공한 레코드를 리스트의 맨 앞으로 보낸다. 
  • 교환하기 : 탐색된 레코드를 맨 앞이 아니라 앞의 레코드와 교환할 수도 있다. 자주 탐색되는 레코드는 점진적으로 앞으로 이동하고 그렇지 않은 레코드는 점진적으로 뒤로 밀린다. 
  •  

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]
                i = i-1
            return i
    return -1

07-3 이진 탐색

• 테이블이 킷값을 기준으로 정렬되어 있다면 이진탐색을 사용. 한 번 비교할 때마다 탐색 범위가 절반으로 준다. 
• 중앙 레코드의 킷값이 탐색 키와 같으면 탐색은 성공한 것이고, 중앙 레코드의 위치를 반환하면 된다.
• 중앙 레코드가 탐색 키보다 크면 그보다 오른쪽에 있는 모든 레코드는 탐색 키보다 크므로 더는 탐색할 필요가 없다. 따라서 왼쪽의 레코드들만 탐색
• 중앙 레코드가 탐색 키보다 작으면 오른쪽만 탐색. 
•  

def binary_search(A, key, low, high):
	if (low <= high):
    	middle = (low + high)//2
        if key == A[midle]:
        	return middle
        elif (key<A[middle]):
        	return bianary_search(A, key, low, middle-1)
        else:
        	return binary_search(A, key, middle + 1, high)

반복 구조

def binary_search_iter(A, key, low, high):
	while (low <= high):
    	middle = (low + high)//2
        if key == A[middle]:
        	return middle
        elif (key > A[middle]):
        	low = middle + 1
        else:
        	high = middle - 1
    return -1

이진 탐색은 얼마나 빠를까요?

• 매 단계에서 탐색 범위가 반으로 줄어든다. 그러므로 O(log2n) 알고리즘이다. 
• 이진 탐색의 특징
  • O(log2n)의 매우 효율적인 탐색 방법
  • 반드시 배열이 정렬되어 있어야 사용할 수 있다.
  • 테이블이 한 번 만들어지면 이후로 변경되지 않고 탐색 연산만 처리한다면 이진 탐색이 최고의 선택 중 하나이다. 
  • 데이터의 삽입이나 삭제가 빈번한 응용에는 이진 탐색이 좋지 않다. 탐새근 효율적이지만 비효율적인 삽입과 삭제 연산이 더 많이 처리된다면 전체적으로 불리하다. 

보간 탐색

• 이진 탐색의 일종으로 탐색 키가 존재할 위치를 예측하여 탐색하는 방법. 
•  

• 레코드의 위치와 그 레코드의 킷값이 비례한다는 가정을 사용. 
• 코드는 이진 탐색 함수에서 middle 계산만 수정
  • middle = int(low+ (high-low) * (key-A[low].key) / (A[high].key-A[low].key))

07-4 이진 탐색 트리

• 이진 탐색은 레코드의 삽입과 삭제가 빈번한 응용에서 비효율적인데, 이를 해결하기 위한 것이 이진 탐색 트리이다. 탐색의 성능은 유지하면서 삽입과 삭제도 효율적으로 처리

이진 탐색 트리의 조건

• 이진 탐색 트리는 모든 노드가 왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다라는 규칙을 따른다.
• 킷값의 중복을 허용하지 않는다. 

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

class BSTNode:
	def __init__(self, key, value):
    	self.key = key
        self.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 searhc_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)

이진 탐색 트리의 삽입 연산

def insert_bst(root, node):
	if root == None:
    	return node
    if node.key == root.key:
    	return root
    
    if node.key < root.key:
    	root.left = insert_bst(root.left, node)
    else:
    	root.right = insert_bst(root.right, node)
    return 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)
    else:
    	if root. left == None:
        	return root.right
        if root.right == None:
        	return root.elft
        
        succ = root.right
        while succ.left != None:
        	succ = succ.left
        
        root.key = succ.key
        root.value = suc.value
        root.right = delete_bst(root.right, succ.key)
	return root