탐색 트리란?
- 탐색을 위한 트리 기반의 자료구조
- 이진 탐색 트리
- 정의
- 모든 노드는 유일한 키를 가짐
- 왼쪽 서브트리의 키들은 루트의 키보다 작음
- 오른쪽 서브트리의 키들은 루트의 키보다 큼
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리임
- 효율적인 탐색을 위한 이진 트리 기반의 자료구조
- 시간 복잡도(삽입/삭제/탐색): O(log₂n)
이진 탐색 트리 구현
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 search_max_bst(n): # 최대 값의 노드 탐색
while n != None and n.right != None:
n = n.right
return n
def search_min_bst(n): # 최소 값의 노드 탐색
while n != None and n.left != None:
n = n.left
return n
def insert_bst(r, n): # 이진탐색트리 삽입연산 (재귀)
if n.key < r.key: # 삽입할 노드의 키가 루트보다 작으면
if r.left is None: # 루트의 왼쪽 자식이 없으면
r.left = n # n은 루트의 왼쪽 자식이 됨
return True
else: # 루트의 왼쪽 자식이 있으면
return insert_bst(r.left, n) # 왼쪽 자식에게 삽입하도록 함
elif n.key > r.key: # 삽입할 노드의 키가 루트보다 크면
if r.right is None: # 루트의 오른쪽 자식이 없으면
r.right = n # n은 루트의 오른쪽 자식이 됨
return True
else: # 루트의 오른쪽 자식이 있으면
return insert_bst(r.right, n) # 오른쪽 자식에게 삽입하도록 함
else: # 키가 중복되면
return False # 삽입 X
def delete_bst_case1(parent, node, root): # 단말노드 삭제
if parent is None: # 삭제할 단말노드가 루트이면
root = None # 공백트리가 됨
else:
if parent.left == node: # 삭제할 노드가 부모의 왼쪽 자식이면
parent.left = None # 부모의 왼쪽 링크를 None
else: # 삭제할 노드가 부모의 오른쪽 자식이면
parent.right = None # 부모의 오른쪽 링크를 None
return root
def delete_bst_case2(parent, node, root): # 자식이 하나인 노드 삭제
if node.left is not None: # 왼쪽 자식만 있을 때
child = node.left
else: # 오른쪽 자식만 있을 때
child = node. right
if node == root: # 삭제할 노드가 루트이면
root = child
else:
if node is parent.left:
parent.left = child # 부모와 왼쪽 자식을 연결
else:
parent.right = child # 부모와 오른쪽 자식을 연결
return root
def delete_bst_case3(parent, node, root): # 자식이 둘인 노드 삭제
succp = node # 후계자의 부모노드
succ = node.right # 후계자노드
while succ.left != None: # 후계자와 부모노드 탐색
succp = succ
succ = succ.left
if succp.left == succ: # 후계자가 왼쪽 자식이면
succp.left = succ.right # 후계자의 오른쪽 자식과 연결
else: # 후계자가 오른쪽 자식이면
succp.right = succ.right # 후계자의 오른쪽 자식과 연결
node.key = succ.key # 후계자의 키를 삭제할 노드에 복사
node.value = succ.value # 후계자의 값을 삭제할 노드에 복사
return root
def delete_bst(root, key): # 이진탐색트리 삭제연산
if root == None: # 공백트리
return None
parent = None # 삭제할 노드의 부모
node = root # 삭제할 노드
while node != None and node.key != key: # 부모 탐색
parent = node
if key < node.key:
node = node.left
else:
node = node.right
if node == None: # 삭제할 노드가 없음
return None
# 삭제할 노드가 단말노드인 경우
if node.left == None and node.right == None:
root = delete_bst_case1(parent, node, root)
# 삭제할 노드의 자식이 하나인 경우
elif node.left == None or node.right == None:
root = delete_bst_case2(parent, node, root)
# 삭제할 노드의 자식이 둘인 경우
else:
root = delete_bst_case3(parent, node, root)
return root
def count_node(n): # 재귀를 이용해 트리의 노드 수를 계산
if n is None:
return 0
else:
return 1 + count_node(n.left) + count_node(n.right)
def count_leaf(n): # 단말노드의 수 계산
if n is None:
return 0
elif n.left == None and n.right == None:
return 1
else:
return count_leaf(n.left) + count_leaf(n.right)
def inorder(n): # 중위 순회
if n is not None:
inorder(n.left)
print(n.key, end=' ')
inorder(n.right)
class BSTMap(): # 이진탐색트리를 이용한 맵
def __init__(self): # 생성자
self.root = None
def isEmpty(self): # 맵 공백 검사
return self.root == None
def clear(self): # 맵 공백상태로 초기화
self.root = None
def size(self): # 노드 수 계산
return count_node(self.root)
def search(self, key): # 노드 탐색
return search_bst(self.root, key)
def findMax(self): # 최대노드 탐색
return search_max_bst(self.root)
def findMin(self): # 최소노드 탐색
return search_min_bst(self.root)
def insert(self, key, value=None): # 삽입
n = BSTNode(key, value)
if self.isEmpty():
self.root = n
else:
insert_bst(self.root, n)
def delete(self, key): # 삭제
self.root = delete_bst(self.root, key)
def display(self, msg='BSTMap: '): # 맵 출력 (중위 순회)
print(msg, end='')
inorder(self.root)
print()
if __name__ == '__main__':
map = BSTMap()
data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
print('[삽입 연산]:', data)
# [삽입 연산]: [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
for key in data:
map.insert(key)
map.display('[중위 순회]: ')
# [중위 순회]: 3 7 12 18 22 26 30 35 68 99
if map.search(26) != None:
print('[탐색 26]: 성공')
else:
print('[탐색 26]: 실패')
# [탐색 26]: 성공
if map.search(25) != None:
print('[탐색 25]: 성공')
else:
print('[탐색 25]: 실패')
# [탐색 25]: 실패
map.delete(3)
map.display('[3 삭제]: ')
# [3 삭제]: 7 12 18 22 26 30 35 68 99
map.delete(68)
map.display('[68 삭제]: ')
# [68 삭제]: 7 12 18 22 26 30 35 99
map.delete(18)
map.display('[18 삭제]: ')
# [18 삭제]: 7 12 22 26 30 35 99
map.delete(35)
map.display('[35 삭제]: ')
# [35 삭제]: 7 12 22 26 30 99
