Programming 기초/Python
[Python 자료구조 #탐색트리2] 이진탐색트리를 이용한 맵
코딩상륙작전
2023. 5. 26. 18:05
* 이진탐색트리를 이용한 맵
↓BSTNode(), inorder(), count_node(),search_bst()함수 코드참고.(이전 블로그 글 참고)
더보기
class BSTNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def inorder(n): # 중위 순회 함수
if n is not None:
inorder(n.left) # 왼쪽 서브트리 처리
print(n.key, end=" ") # 루트노드 처리(화면 출력)
inorder(n.right)
def count_node(n):
if n is None:
return 0
else:
return 1 + count_node(n.left) + count_node(n.right)
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)
이진탐색트리(Binary Search tree)을 이용한 Map 구현
# BSTMap의 ADT 구현
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 searchValue(self, key):
return search_value_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): # 삭제 연산
delete_bst(self.root, key)
def display(self, msg="BSTMap :"):
print(msg, end="")
inorder(self.root)
print()
map = BSTMap()
data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
print("[삽입 연산] : ", data)
for key in data:
map.insert(key)
map.display("[중위 순회] : ")
if map.search(26) != None: # 탐색연산 테스트
print("[탐색 26 ] : 성공")
else:
print("[탐색 26 ] : 실패")
if map.search(25) != None: # 탐색연산 테스트
print("[탐색 25 ] : 성공")
else:
print("[탐색 25 ] : 실패")
map.delete(3) # 삭제연산 테스트
map.display("[ 3 삭제] : ")
map.delete(68) # 삭제연산 테스트
map.display("[ 68 삭제] : ")
map.delete(18) # 삭제연산 테스트
map.display("[ 18 삭제] : ")
map.delete(35) # 삭제연산 테스트
map.display("[ 35 삭제] : ")
----------------------------------------------------------
[삽입 연산] : [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
[중위 순회] : 3 7 12 18 22 26 30 35 68 99
[탐색 26 ] : 성공 # 26은 트리에 있고
[탐색 25 ] : 실패 # 25는 트리에 없음
[ 3 삭제] : 7 12 18 22 26 30 35 68 99
[ 68 삭제] : 7 12 18 22 26 30 35 99
[ 18 삭제] : 7 12 22 26 30 35 99
[ 35 삭제] : 7 12 22 26 30 99