1. 이진 탐색 알고리즘(binary search algorithm)
정렬된 데이터로 된 리스트(배열이나 연결 리스트)가 인수로 들어왔을 때 요소 중에 찾고자 하는 데이터가 있는지 알아보는 알고리즘 →
def binary_search(li, target):
# li: 정렬된 리스트
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
2. 이진 탐색 트리(binary search tree, BST)
-
노드에 직접 데이터 저장 X → 데이터에 대한 참조만 저장(키)
-
모든 키는 유일
-
어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 서브 트리의 그 어떤 키보다 큼
-
어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 서브 트리의 그 어떤 키 값보다 작음
-
노드의 서브 트리도 이진 탐색 트리
-
대부분의 경우, 트리 높이 h는 (아닌 경우도 있음)
2-1. 이진 탐색 트리의 활용
-
집합, 딕셔너리 → 내부적으로 이진 탐색 변형인 균형 이진 탐색 트리 사용
-
딕셔너리 구현 → BST(균형 이진 트리 - 레드 블랙 트리), 해시 테이블
2-2. 이진 탐색 트리의 단점
-
이진 탐색 트리에 데이터가 정렬되어 삽입되는 경우 편향 이진 트리를 나타낼 수 있고, 이 때 삽입, 삭제, 탐색 모두 이다.
-
앞선 문제를 보완한 이진 탐색 트리가 균형 이진 트리이다.
-
균형 이진 트리는 편향 이진 트리가 되지 않도록 자동으로 트리 높이를 낮춰 최악의 경우라도 이 되도록 함
3. 이진 탐색 트리 구현
3-1. 트리 노드 구현
class TreeNode:
def __init__(self, key):
self.__key = key
self.left = None
self.right = None
self.parent = None
def __del__(self):
print('key {} is deleted'.format(self.__key))
@property
def key(self):
return self.__key
@key.setter
def key(self, key):
self.__key = key
@property
def left(self):
return self.__left
@left.setter
def left(self, left):
self.__left = left
@property
def right(self):
return self.__right
@right.setter
def right(self, right):
self.__right = right
@property
def parent(self):
return self.__parent
@parent.setter
def parent(self, p):
self.__parent = p
3-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(cur.left, func):
if not cur:
return
self.inorder_traverse(cur.left, func)
func(cur)
self.inorder_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
3-3. 삽입, 삭제, 탐색 함수 구현
-
BST.insert(key): 새로운 키 삽입 -
BST.search(target): target을 키로 가지는 노드를 찾아 반환 -
BST.delete(target): target을 키로 가지는 노드 삭제 -
BST.min(node): 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 작은 key를 가진 노드를 반환 -
BST.max(node): 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 큰 key를 가진 노드를 반환 -
BST.prev(cur): 정렬된 상태에서 cur 노드의 바로 이전 노드를 찾아 반환 -
BST.next(cur): 정렬된 상태에서 cur 노드의 바로 다음 노드를 찾아 반환
- 삽입 (insert)
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
- 탐색(search)
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
- 삭제 (delete)
- 삭제하려는 노드가 리프 노드인 경우, 자식이 하나만 있는 노드인 경우, 자식이 둘인 경우에 따라 나누어 삭제
- 자식 노드가 두 개일 대는 대체 노드를 찾아 키 값을 교환한 후 대체 노드를 삭제함
- 대체 노드는 반드시 리프 노드이거나 왼쪽 자식만 있는 노드
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_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(repalce)
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
- min, max
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
- prev, next
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
