[ALGORITHM] Binary Search Tree (이진 탐색 트리)

Ellie Kang·2022년 6월 16일
0

ALGORITHM

목록 보기
2/2

바로 전 포스트에서 Binary Search 알고리즘에 대해 다뤘는데, 이 포스트에서는 이진 탐색에서 좀 더 나아간 이진 탐색 트리 (Binary Search Tree) 에 대해서 다뤄보겠다 🌳
타이핑이 귀찮기 때문에 간략히 BST 라고 부르겠다... (BTS랑 헷갈령 ㅋㅋㅋ... 미안해.)


📖 Binary Search Tree

  • Binary Search Tree is a tree data structure in which each node has at most two children, which are referred to as the left subtree and the right subtree
  • First node is the Base Node that is placed at the top
  • Nodes after the base node are designed to be in left/ right subtree
    (if less than BN -> left subtree, greater than BN -> right subtree)

BST에서는 트리를 traverse 하는 순서도 중요한데, 대표적으로 In- / Pre- / Post- Order Traverse로 나눌 수 있다.


(cred: leetcode)

➡️ In-Order Traversing

이 트래버싱은 left_subtree -> base node -> right_subtree 순서로 트리를 훑는 방법이다.

➡️ Pre-Order Traversing

이 트래버싱은 base node -> left_subtree -> right_subtree 순서로 트리를 순회한다.

➡️ Post-Order Traversing

이 트래버싱은 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)이 되겠다.

그럼 바이너리 안녕 🎶

profile
I DO CODE!

0개의 댓글