8.1. 이진탐색 알고리즘(binary search algorithm)

정렬된 데이터로 된 리스트(배열이나 연결 리스트)가 인수로 들어왔을 때 요소 중에 찾고자 하는 데이터가 있는지 알아보는 알고리즘

def binary_search(li, target):
    start = 0
    end = len(li) -1

    while start <= end:
        middle = (start+end)//2
        if li[middle]==target:
            return middle
        elif li[middle]>target:
            end = middle - 1
        else:
            start = middle + 1
    
    return None

• 매개변수 : 정렬된 리스트와 찾고자 하는 값을 받음
• 성능 : O(log n)
  -> 요소들이 정렬되었다는 전제조건이 있음.
• if li[middle]>target: end = middle - 1 : middle이 target보다 크다면, target은 middle 값을 넘을 리 없기 때문에 end값을 middle 보다 하나 작은 값으로 설정
• 그 외의 경우 middle값보다 target값이 크기 때문에 start값을 middle보다 하나 큰 값으로 설정

이진 탐색 트리 : 데이터 삽입, 삭제, 탐색 모두 성능 O(log n)

8.2. 딕셔너리

딕셔너리 : <key, item> 쌍으로 된 집합

8.3. 이진 탐색 트리

• 노드에 데이터를 직접 저장하지 않음 = 데이터에 대한 참조만 저장.

  데이터의 참조를 저장하고 있는 노드를 나타내는 키

1) 모든 키는 유일키
2) 어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 노드의 어떤 키 값보다도 큼
3) 어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 노드의 어떤 키 값보다도 작음
4) (재귀적 정의)노드의 서브트리도 이진 탐색 트리

1) ADT

1-1) Object

• 유일한 키 값을 가진 집합 노드

1-2) Operation

1) BST.insert(key) : 새로운 키 삽입
2) BST.search(target) : target을 키로 가지는 node 반환
3) BST.delete(target) : target을 키로 가지는 node 삭제
4) BST.min(node) : 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 작은 key값을 가진 node 반환
5) BST.max(node) : 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 큰 key값을 가진 node 반환
6) BST.prev(cur) : 정렬된 상태에서 cur노드의 바로 이전 노드를 찾아 반환
7) BST.next(cur) : 정렬된 상태에서 cur노드의 바로 다음 노드를 찾아 반환

2) 구현

class BST:
    def __init__(self):
        self.root = None
    
    def get_root(self):
        return self.root

    def preorder_traverse(self, cur, func):
        if not cur:
            return
        
        func(cur)
        self.preorder_traverse(cur.left, func)
        self.preorder_traverse(cur.right, func)

    def inorder_traverse(self, cur, func):
        if not cur:
            return
        
        self.preorder_traverse(cur.left, func)
        func(cur)
        self.preorder_traverse(cur.right, func)

    def __make_left(self, cur, left):
        cur.left = left
        if left:
            left.parent = cur

    def __make_right(self, cur, right):
        cur.right = right
        if right:
            right.parent = cur

• make_left, make_right 함수 : cur 노드의 왼쪽 자식을 left로, 오른쪽 자식을 right로 만들어줌
  -> Tree 멤버에 parent가 있기 때문에 부모 노드의 참조에 자식 노드를 연결할 때는 반드시 자식 노드의 parent 참조도 부모를 가리켜야 함

2-1) 삽입

def insert(self, key):
        new_node = TreeNode(key)

        cur = self.root
        if not cur :
            self.root = new_node
            return

        while True:
            parent = cur
            if key < cur.key:
                cur = cur.left
                if not cur:
                    self.__make_left(parent, new_node)
                    return
            else:
                cur = cur.right
                if not cur:
                    self.__make_right(parent, new_node)
                    return

ex) 3-6인 노드에 5 추가 삽입 하는 경우,
5는 6의 왼쪽 서브트리에 위치해야 하기에 노드 6의 왼쪽 자식으로 내림
이 때 5의 parent는 노드 6이 됨.
5는 3보다 크므로 3의 오른쪽 서브트리에 위치해야 하므로, 이 때 5의 parent는 노드 3이 됨.
cur은 None이 되므로 parent의 오른쪽 자식 노드를 가리키는 참조에 따라 5가 삽입됨.

2-2) 탐색

def search(self, target):
        cur = self.root
        while cur :
            if cur.key == target :
                return cur
            elif cur.key > target:
                cur = cur.left
            elif cur.key < target:
                cur = cur.right
        return cur

• target이 있다면 cur을 기준으로 아래로 쭉 훑으면서 비교

2-3) 삭제

• 삭제하려는 노드가 리프노드인지, 자식이 하나만 있는 노드인지, 자식이 둘이 있는 노드인지 나눠서 삭제해야 함

def __delete_recursion(self, cur, target):
        if not cur:
            return None
        elif target < cur.key: # 삭제하려는 노드가 현재 노드보다 작을 때
            new_left = self.__delete_recursion(cur.left, target)
            self.__make_left(cur, new_left)
        elif target > cur.key: # 삭제하려는 노드가 현재 노드보다 큰 경우
            new_right = self.__delete_recursion(cur.right, target)
            self.__make_right(cur, new_right)
        else:
            if not cur.left and not cur.right: #리프 노드인 경우
                cur = None
            elif not cur.right: # 자식이 하나인 경우 : 왼쪽만 존재
                cur = cur.left
            elif not cur.left:# 자식이 하나인 경우 : 오른쪽만 존재
                cur = cur.right
            else: # 자식이 둘인 경우
                replace = cur.left
                replace = self.max(replace)
                cur.key, replace.key = replace.key, cur.key
                new_left = self.__delete_recursion(cur.left, replace.key)
                self.__make_left(cur, new_left)
        return cur

    def delete(self, target):
        new_root = self.__delete_recursion(self.root, target)
        self.root = new_root

• 삭제하려는 노드가 target보다 크거나 작다면 재귀 함수 호출하여 target으로 접근함

ex1) 4-5-6으로 왼쪽 서브트리만 존재하는 트리에서 5 삭제.
-> target에 접근할 때까지 재귀 함수를 돌게 됨.
노드 5의 경우 왼쪽 서브트리가 존재하기 때문에 cur=cur.left가 실행되며 해당 값(노드 4)이 new_left로 반환됨.
self.__make_left(cur, new_left) 를 통해 5가 삭제된 후 4와 6 노드를 연결하고 cur값을 parent로 리턴함.
new_root = self.__delete_recursion(self.root, target) : 리턴된 cur 값은 parent값이기 때문에 새로운 루트가 됨

ex2) 삭제하려는 노드가 리프노드인 경우.
-> cur이 None을 반환하기 때문에 parent와 연결된 노드 없음

ex3) 자식 노드가 두 개일 경우.

• 자식 노드 직접 삭제가 아닌 대체 노드를 찾아 키 값을 교환한 후 대체 노드를 대신 삭제함
• 대체 노드 : 반드시 리프노드이거나 노드값이 한 개만 존재하는 서브트리
  -> replace는 삭제 노드의 왼쪽 서브트리를 가리키며, 자식 노드 중에서 최대 값을 찾아 cur과 replace의 키 값을 교환함. 리프노드가 된 삭제하고자 한 노드를 삭제처리.

2-4) 최대, 최소

def min(self, cur):
        while cur.left != None:
            cur = cur.left
        return cur
    
    def max(self, cur):
        while cur.right != None:
            cur = cur.right
        return cur

• 최대 : right로 계속 따라 내려가면 됨
• 최소 : left로 계속 따라 내려가면 됨

2-5) 해당 노드의 이전 값, 다음 값

	def prev(self, cur):
        if cur.left:
            return self.max(cur.left)
        
        parent = cur.parent
        while parent and cur == parent.left:
            cur = parent
            parent = parent.parent

        return parent

    def next(self, cur):
        if cur.right:
            return self.min(cur.right)

        parent = cur.parent
        while parent and cur == parent.right:
            cur = parent
            parent = parent.parent

        return parent
        

• prev() : 이전 원소를 가져옴
  1) 왼쪽 자식 노드가 있는 경우 : 해당 왼쪽 트리에서 가장 큰 노드값을 구하면 됨. 즉 해당 노드를 만날 때까지 계속해서 타고 내려감.
• next() : 다음 원소를 가져옴
  1) 오른쪽 트리에서 가장 작은 노드값을 구하면 됨.

bst = BST()

bst.insert(6)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(5)
bst.insert(8)
bst.insert(10)
bst.insert(9)
bst.insert(11)

f = lambda x: print(x.key, end=' ')
bst.inorder_traverse(bst.get_root(), f)

searched_node = bst.search(8)
if searched_node:
        print(f'searched key : {searched_node.key}')

        prev_node = bst.prev(searched_node)
        if prev_node:
            print(f'prev key : {prev_node.key}')
        else:
            print(f'this is the first key of the BST')

        next_node = bst.next(searched_node)
        if next_node:
            print(f'next key : {next_node.key}')
        else:
            print(f'this is the last key of the BST')
else:
        print('there is no such key')
print()

• 중위 순회한 값을 통해 정렬 확인

3) 단점

• 편향 이진 트리의 경우, 성능 O(n)