[자료구조와알고리즘with파이썬] ch.7-4 이진 탐색 트리

순차 탐색

리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
→ 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하다. → 시간복잡도는 O(N)

하늘	바다	바나나	포도
확인

하늘	바다	바나나	포도
	확인

하늘	바다	바나나	포도
		확인, 성공

# 순차 탐색 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로)

# 탐색하고자 하는 리스트
fruit = ["apple", "banana", "orange", "grape", "mango"]
# 리스트의 길이
len_fruit = len(fruit)

print(sequential_search(len_fruit, "orange", fruit))

https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%88%9C%EC%B0%A8-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89

[알고리즘] 탐색 - 순차 탐색, 이진 탐색

 

---

이진(이분) 탐색

- 이미 정렬되어 있는 데이터에서 특정한 값을 찾아내는 알고리즘
- 시간복잡도: O(log n)  ∵ 한 번 확인할 때마다 확인해야 하는 원소의 개수가 절반씩 줄어든다.
- 시작점, 끝점, 중간점 →  찾으려는 데이터와 중간점의 값을 비교
- 삽입과 삭제가 빈번한 곳에서는 사용하기 어렵다.

찾으려는 데이터 < 중간점	왼쪽 탐색 (끝점을 중간점 이전으로 옮긴다.)
찾으려는 데이터 > 중간점	오른쪽 탐색 (시작점을 중간점 이후로 옮긴다.)

 

0	1	2	3	4	5	6	7	8	9
시작점				중간점					끝점

0	1	2	3	4	5	6	7	8	9
					시작점		중간점		끝점

0	1	2	3	4	5	6	7	8	9
					시작점, 중간점	끝점

0	1	2	3	4	5	6	7	8	9
						시작점, 끝점, 중간점

 
[반복문 사용]

def binary_search_iter(A, key, low, high):
    while (low <= high):            # 검색해야 할 레코드가 있는 경우
        middle = (low + high) // 2  # middle 계산
        if key == A[middle]:        # 탐색 성공 O(1)
            return middle           # 중앙 레코
        elif (key < A[middle]):     # 왼쪽 부분 리스트 (low ~ middle-1) 탐색
            high = middle - 1
        else:                       # 오른쪽 부분 리스트 (middle+1 ~ high) 탐색
            low = middle + 1
    return -1                       # 탐색 실패

 
[재귀 사용]

def binary_search(A, key, low, high):
    if (low <= high):               # 검색해야 할 레코드가 있는 경우
        middle = (low + high) // 2  # middle 계산
        if key == A[middle]:        # 탐색 성공 O(1)
            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                       # 탐색 실패

[자료구조와 알고리즘 with Python] Chapter 7 : Search

 

---

이진 탐색 트리 (Binary Search Tree)

: 효율적인 데이터의 삽입과 삭제 가능
: 왼쪽 자식노드 == 작은 값, 오른쪽 자식 노드 == 큰 값
: 탐색을 위한 키(key) 와 나머지 데이터 부분(value)
: 왼쪽과 오른쪽 서브트리도 이진 탐색 트리임

# 코드 7.5: 이진 탐색 트리를 위한 노드 클래스
class BSTNode:
    def __init__(self, key, value):
        self.key = key      # 키(key)
        self.value = value  # 값(value)
        self.left = None
        self.right = None

 
[1. key를 이용한 탐색 (순환, 반복)]

# 코드 7.6: 이진 탐색 트리의 탐색 연산(순환 구조)
def search_bst(n, key):
    if n == None:
        return None
    elif key == n.key:
        return n    # 탐색 성공
    elif key < n.key: #주어진 키 값이 루트 노드의 키값(n.key)보다 작은 경우
        return search_bst(n.left, key)    # 왼쪽 서브트리에서 탐색
    else: #주어진 키 값이 루트 노드의 키값(n.key)보다 큰 경우
        return search_bst(n.right, key)   # 오른쪽 서브트리에서 탐색

# 코드 7.6.1: 이진 탐색 트리의 탐색 연산(반복 구조)
# key: 찾으려는 키값, n: 현재 노드
def search_bst_iter(n, key):
    while n != None:
        if key == n.key:
            return n    # 탐색 성공
        elif key < n.key:
            n = n.left      # 왼쪽 서브트리에서 탐색
        else:
            n = n.right     # 오른쪽 서브트리에서 탐색
    return None

 
[2. value를 이용한 탐색 (전위 순회)]

# 코드 7.7: 이진 탐색 트리의 값을 이용한 탐색(전위순회)
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)    # 오른쪽 서브트리에서 탐색

 
[이진 탐색 트리 삽입]

# 코드 7.8: 이진 탐색 트리의 삽입 연산
def insert_bst(root, node):
    if root == None:    # 공백 노드에 도달하면, 이 위치에 삽입 (탐색에 성공하지 않아야 한다.)
        return node     # node를 반환
    if node.key == root.key:
        return 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

 
[이진 탐색 트리 삭제]
노드 탐색 후 →

1) 삭제하려는 노드가 단말노드인 경우

2) 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우 (자식 하나)

3) 2개의 자신을 가진 경우

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

 

# 코드 7.9: 이진 탐색 트리의 삭제 연산
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:
        # Case 1 (단말 노드) or Case 2 (오른쪽 자식만 있는 경우)
        if root.left == None:
            return root.right
        
        # Case 2 (왼쪽 자식만 있는 경우)
        elif root.right == None:
            return root.left
        
        # Case 3 (두 자식이 모두 있는 경우)
        # succ: 후계자 노드
        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

 

[자료구조와 알고리즘 with Python] Chapter 7 : Search