바로 전 포스트에서 Binary Search 알고리즘에 대해 다뤘는데, 이 포스트에서는 이진 탐색에서 좀 더 나아간 이진 탐색 트리 (Binary Search Tree) 에 대해서 다뤄보겠다 🌳
타이핑이 귀찮기 때문에 간략히 BST 라고 부르겠다... (BTS랑 헷갈령 ㅋㅋㅋ... 미안해.)
BST에서는 트리를 traverse 하는 순서도 중요한데, 대표적으로 In- / Pre- / Post- Order Traverse로 나눌 수 있다.
(cred: leetcode)
이 트래버싱은 left_subtree -> base node -> right_subtree 순서로 트리를 훑는 방법이다.
이 트래버싱은 base node -> left_subtree -> right_subtree 순서로 트리를 순회한다.
이 트래버싱은 In-order와 좀 비슷한데, left_subtree -> right_subtree -> base node 순서로 트리를 훑는다.
여기서 주의할 점은, 각 subtree의 제일 deep한 레벨의 노드부터 먼저 훑기 때문에 헷갈리지 않길 바람 😵💫
위에 사진에서 보다시피 DFS (Depth-First Search)와 BFS (Breath-First Search)로 나뉘는데, 이건 나중 포스트에서 더 자세히 다뤄보겠다.
아래 코드에는 위에서 언급한 세가지 traversing 펑션과, 트리의 child를 넣는 펑션, 특정 값이 있는지 서치하는 펑션과, minimum, maximum, total sum을 리턴하는 펑션을 구현해보겠다.
class BST:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add_child(self, data):
if data == self.data:
return # BST does not allow any duplicates
if data < self.data:
if self.left:
self.left.add_child(data)
else:
self.left = BST(data)
else:
if self.right:
self.right.add_child(data)
else:
self.right = BST(data)
def inOrder(self):
elements = []
if self.left:
elements += self.left_inOrder()
elements.append(self.data)
if self.right:
elements += self.right_inOrder()
return elements
def postOrder(self):
elements = []
if self.left:
elements += self.left.postOrder()
if self.right:
elements += self.right.postOrder()
elements.append(self.data)
return elements
def preOrder(self):
elements = [self.data]
if self.left:
elements += self.left.preOrder()
if self.right:
elements += self.right.preOrder()
return elements
def search(self, val):
if self.data == val:
return True
if self.data > val:
if self.left:
return self.left.search(val)
else:
return False
if self.data < val:
if self.right:
return self.right.search(val)
else:
return False
def findMin(self):
if self.left is None:
return self.data
return self.left.findMin()
def findMax(self):
if self.right is None:
return self.data
return self.right.findMax()
def totalSum(self):
lsum = self.left.totalSum() if self.left else 0
rsum = self.right.totalSum() if self.right else 0
return self.data + lsum + rsum
휴 힘들다.
이처럼 BST는 Tree Structure의 한 종류로서 Binary Search를 공부하면 쉽게 이해할 수 있는 유용한 알고리즘이다.
이진 탐색 문제를 풀 때, Array던 트리던 무조건 머릿속으로 그려봐야 더 손쉽게 코드를 짤 수 있는 것 같다!
BST의 시간 복잡도는 Binary Search와 같이 O(logn)이 되겠다.
그럼 바이너리 안녕 🎶