BST
이진 탐색 트리란?
지금까지 우리는 신명나게 트리를 만들고, 이진탐색 트리를 만들고, 결정트리를 만들었다. 이젠, 트리로 탐색을 할 차례이다.
탐색의 원리
이진탐색트리의 각 노드에는 키값, 그리고 value가 들어간다. 일단 value는 당장 사용하지 않을것이기에 None, 혹은 ABCD 순으로 저장한다고 가정하자. 이진 트리의 특성상, 부모보다 키가 작은 노드는 좌측 자식, 큰 값을 우측 자식이 된다. 이를 이용해서 탐색을 하면 된다. 사실 결정트리랑 거의 비슷하다. 다만 BST에서의 삭제는 특이한 점이 많이 있다 .
우선 코드를 살펴보도록 하자
BST 구현
from CircularQueue import *
class BSTNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
class BST:
def search_bst(self, n, key):
if n is None:
return None
elif key == n.key:
return n
elif key < n.key:
return self.search_bst(n.left, key)
else:
return self.search_bst(n.right, key)
def search_bst_iter(self, n, key):
while n is not None:
if key == n.key:
return n
elif key < n.key:
n = n.left
else:
n = n.right
return None
def search_value_bst(self, n, value):
if n is None:
return None
elif value is n.value:
return n
temp = self.search_value_bst(n.left, value)
if temp is not None:
return temp
else:
return self.search_value_bst(n.right, value)
def search_max_bst(self, n):
while n is not None and n.right is not None:
n = n.right
return n
def search_min_bst(self, n):
while n is not None and n.left is not None:
n = n.left
return n
def insert_bst(self, r, n):
if n.key < r.key:
if r.left is None:
r.left = n
return True
else:
return self.insert_bst(r.left, n)
elif n.key > r.key:
if r.right is None:
r.right = n
return True
else:
return self.insert_bst(r.right, n)
else:
return False
def delete_bst_case1(self, parent, node, root):
if parent is None:
root = None
else:
if parent.left is node:
parent.left = None
else:
parent.right = None
return root
def delete_bst_case2(self, parent, node, root):
if node.left is None:
child = node.right
else:
child = node.left
if node == root:
root = child
else:
if node is parent.left:
parent.left = child
else:
parent.right = child
return root
def delete_bst_case3(self, node, root):
succp = node
succ = node.right
while succ.left is not None:
succp = succ # one step donw
succ = succ.left # succeed to left
if succp.left is succ:
succp.left = succ.right
else:
succp.right = succ.right
node.key = succ.key
node.value = succ.value
node = succ
return root
def delete_bst(self, root, key):
if root is None:
return None
parent = None
node = root
while node is not None and node.key is not key:
parent = node
if key < node.key:
node = node.left
else:
node = node.right
if node is None:
return None
if node.left is None and node.right is None:
root = self.delete_bst_case1(parent, node, root)
elif node.left is None or node.right is None:
root = self.delete_bst_case2(parent, node, root)
else:
root = self.delete_bst_case3(node, root)
return root
def preorder(self, node):
if node is not None:
print(node.key, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(node.key, end=' ')
self.inorder(node.right)
def postorder(self, node):
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print(node.key, end=' ')
def levelorder(self, root):
qu = CircularQueue()
qu.enqueue(root)
while not qu.isEmpty():
node = qu.dequeue()
if node is not None:
print(node.key, end=' ')
qu.enqueue(node.left)
qu.enqueue(node.right)
def count_node(self, n):
if n is None:
return 0
else:
return 1 + self.count_node(n.left) + self.count_node(n.right)
def count_leaf(self, n):
if n is None:
return 0
elif n.left is None and n.right is None:
return 1
else:
return self.count_leaf(n.left) + self.count_leaf(n.right)
def calc_height(self, n):
if n is None:
return 0
hleft = self.calc_height(n.left)
hright = self.calc_height(n.right)
if hleft > hright:
return hleft + 1
else:
return hright + 1
# ---------------------------------
# driver code
# 노드 만들기 연산
def main():
node_0 = BSTNode(18, 'a')
node_1 = BSTNode(7, 'b')
node_2 = BSTNode(3, 'c')
node_3 = BSTNode(12, 'd')
node_4 = BSTNode(26, 'e')
node_5 = BSTNode(31, 'f')
node_6 = BSTNode(27, 'g')
B = BST() # B를 탐색리스트로 선언
# 삽입 연산
B.insert_bst(node_0, node_0) # 루트 노드 삽입
B.insert_bst(node_0, node_1)
B.insert_bst(node_0, node_2)
B.insert_bst(node_0, node_3)
B.insert_bst(node_0, node_4)
B.insert_bst(node_0, node_5)
B.insert_bst(node_0, node_6)
# 전위 중위 후위 레벨 노드 갯수, 높이, 리프노드 출력
print("Pre-Order : ", end='')
B.preorder(node_0)
print()
print("In-Order : ", end='')
B.inorder(node_0)
print()
print("Post-Order : ", end='')
B.postorder(node_0)
print()
print("Level-Order : ", end='')
B.levelorder(node_0)
print()
print("노드의 개수 = ", end='')
print(B.count_node(node_0))
print("단말의 개수 = ", end='')
print(B.count_leaf(node_0))
print("트리의 높이 = ", end='')
print(B.calc_height(node_0))
print()
print('----------------------------------------------------')
print('탐색 연산')
print('1. 존재하는 키 탐색')
print(B.search_bst(node_0, 12)) # 존재하는 키
print('2. 검증 (탐색노드는 3번노드와 동일함)')
print(B.search_bst(node_0, 12) == node_3) # 검증을 위해 실제 노드와 일치하는지 비교
print('3. 존재하지 않는 키')
print(B.search_bst(node_0, 38)) # 존재하지 않는 키
print()
print('----------------------------------------------------')
print('삽입 연산')
node_7 = BSTNode(38, 'h')
B.insert_bst(node_0, node_7)
# 삽입 확인
print("Pre-Order : ", end='')
B.preorder(node_0)
print()
print("노드의 개수 = ", end='')
print(B.count_node(node_0))
print()
print('----------------------------------------------------')
# 삭제
print('삭제')
print("Level-Order : ", end='')
B.levelorder(node_0)
print()
print('1. 단말 노드 삭제')
B.delete_bst(node_0, 3)
print("Level-Order : ", end='')
B.levelorder(node_0)
print()
print('2.자식이 하나인 노드 삭제')
B.delete_bst(node_0, 7)
print("Level-Order : ", end='')
B.levelorder(node_0)
print()
print('3.자식이 둘인 노드 삭제')
B.delete_bst(node_0, 31)
print("Level-Order : ", end='')
B.levelorder(node_0)
print()
if __name__ == "__main__":
main()
코드가 엄청 길지만, 하나씩 살펴보도록 하자.
탐색 기능
def search_bst(self, n, key):
if n is None:
return None
elif key == n.key:
return n
elif key < n.key:
return self.search_bst(n.left, key)
else:
return self.search_bst(n.right, key)
def search_bst_iter(self, n, key):
while n is not None:
if key == n.key:
return n
elif key < n.key:
n = n.left
else:
n = n.right
return None
def search_value_bst(self, n, value):
if n is None:
return None
elif value is n.value:
return n
temp = self.search_value_bst(n.left, value)
if temp is not None:
return temp
else:
return self.search_value_bst(n.right, value)
def search_max_bst(self, n):
while n is not None and n.right is not None:
n = n.right
return n
def search_min_bst(self, n):
while n is not None and n.left is not None:
n = n.left
return n탐색을 담당하는 부분의 코드는 다음과 같다.
복잡해 보이지만, 원리는 단 하나이다. 키 값이 작으면 왼쪽, 크면 오른쪽이다. 나머지는 recursion과 while반복문, value값으로 search 이정도의 차이일 뿐이다.
삽입 연산
def insert_bst(self, r, n):
if n.key < r.key:
if r.left is None:
r.left = n
return True
else:
return self.insert_bst(r.left, n)
elif n.key > r.key:
if r.right is None:
r.right = n
return True
else:
return self.insert_bst(r.right, n)
else:삽입은 탐색과 비슷한 과정을 가진다. 루트노드에서부터 시작, 키 값 비교를 통해 더 작은 값은 왼쪽, 더 큰 값은 오른쪽으로 이동한다. 만약 이동중에 더 이상 왼쪽, 혹은 오른쪽 노드가 없는 노드까지 온다면, 그곳에 자신을 연결하는 방식이다.
지금까지는 그렇게 어렵지 않고 트리만 이해하고 있다면 쉽게 이해할 수 있는 메소드들이다. 이젠 진짜 문제를 살펴보도록 하겠다.
삭제연산
이제 제일 복잡한 삭제연산의 시간이다.
우선 삭제에는 3가지 경우의 수가 존재할 수 있다.
- 노드가 말단노드인 경우
이 경우 단순히 부모노드와의 연결을 끊어버리면 된다.
def delete_bst_case1(self, parent, node, root):
if parent is None:
root = None
else:
if parent.left is node:
parent.left = None
else:
parent.right = None
return root -
노드가 하나의 자식이 있는 경우
자식을 부모, 즉 자신의 할아버지와 연결 한 후 삭제를 한다.def delete_bst_case2(self, parent, node, root): if node.left is None: child = node.right else: child = node.left if node == root: root = child else: if node is parent.left: parent.left = child else: parent.right = child return root
- 노드가 두개의 자식이 있는 경우
이 경우가 기징 복잡하다. 우선 삭제 노드와 가장 유사한 값을 찾아야한다. 삭제할 노드를 기준으로 좌측 서브트리의 가장 오른쪽, 우측 서브트리의 가장 왼쪽이 자기 자신과 가장 가까운 값이 된다. 이를 후계자 노드(succ)라 칭한다. 그 후, 후계자 노드를 자기자신과 자리를바꾸고, 후계자의 자식(succ.right or succ.left)을 후계자의 부모(succp)에 연결한다.
def delete_bst_case3(self, node, root):
succp = node
succ = node.right
while succ.left is not None:
succp = succ # one step donw
succ = succ.left # succeed to left
if succp.left is succ:
succp.left = succ.right
else:
succp.right = succ.right
node.key = succ.key
node.value = succ.value
node = succ
return root- 이를 구별하여 실행하기
각 노드가 말단인지, 자식이 몇개인지 판단하는것은 다른 메소드를 통해서 발생한다. 일단 이 메소드에서는 루트노드를 받고 키 값을 통해 삭제할 노드를 탐색한다. 탐색이 끝났으면 다음과 같은 조건을 통해 노드의 정보를 파악한다.
좌측, 우측 노드가 모두 None이면 말단 노드
좌측 혹은 우측만 있다면 자식 한개
그 외는 자식이 두개
def delete_bst(self, root, key):
if root is None:
return None
parent = None
node = root
while node is not None and node.key is not key:
parent = node
if key < node.key:
node = node.left
else:
node = node.right
if node is None:
return None
if node.left is None and node.right is None:
root = self.delete_bst_case1(parent, node, root)
elif node.left is None or node.right is None:
root = self.delete_bst_case2(parent, node, root)
else:
root = self.delete_bst_case3(node, root)
return root그 밖의 기능
그 밖에 기능들은 모두 트리에서 이미 구현했던 기능들이다. 따라서 트리를 안다면 모두 이해할 수 있을 것이다.
BST MAP
일일히 노드를 생성해야하는 BST와 다르게, 리스트를 가지고 활용할 수 있는 BSTMap 역시 존재한다. 작동원리는 크게 다르지 않기에 코드만 올려놓도록 하겠다
from BST import BST
class BSTNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
class BSTMap(BST):
def __init__(self):
self.root = None # the reason why we only need root
def isEmpty(self):
return self.root is None
def clear(self):
self.root = None
def size(self):
return BST.count_node(self, self.root)
def search(self, key):
return BST.search_bst(self, self.root, key)
def searchValue(self, key):
return BST.search_value_bst(self, self.root, key)
def findmax(self):
return BST.search_max_bst(self, self.root)
def findmin(self):
return BST.search_min_bst(self, self.root)
def insert(self, key, value=None):
n = BSTNode(key, value)
if self.isEmpty():
self.root = n
else:
BST.insert_bst(self, self.root, n)
def delete(self, key):
return BST.delete_bst(self, self.root, key)
def display(self, msg = "BSTMap : "):
print(msg, end='')
BST.inorder(self, self.root)
print()
def main():
map = BSTMap()
data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
print("insertion : ", data)
for key in data:
map.insert(key)
map.display("Inorder : ")
if __name__ == "__main__":
main()
