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)
returnex) 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)
