BST(Binary Search Tree)

bst property : parent보다 작은 수는 left subtree, parent 보다 큰 수는 right subtree에 속하게 된다.

실제로 문제에도 자주 나오고 구현을 알아야할 Tree는 BST이다. BST는 위 property를 만족하는 모든 binary tree를 의미한다.

BST 구현

TreeNode class를 만들고 이를 이용하여 BST class를 만들어 주면 된다. BST에서 만들어 줘야 하는 method는 다음과 같다.

• search
• insert
• delete

시작해보자

TreeNode

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.leftNode = None
        self.rightNode = None

여기부터가 BinarySearchTree이다.

BinarySearchTree

root를 지정해 준다.

class BinarySearchTree:
    def __init__(self, root=None):
    	self.root = root

search : 특정 val이 tree 안에 있는지 확인한다.

def __searchHelp(self, curNode, val):
    #base case
    if not curNode:
    	return None
    elif val == curNode.val:
    	return curNode
    
    #recursive case
    elif val < curNode.val:
    	return __searchHelp(curNode.leftNode, val)
    else:
    	return __searchHelp(curNode.rightNode, val)
        
def search(self, val):
    return __searchHelp(self.root, val)

help function 만들어 사용하고, recursive하게 찾아나간다. 결과로는 해당 node를 return 한다.

insert : 특정 val을 tree안에 주입한다.

def __insertHelp(self, curNode, val):
    # base case
    if not curNode:
    	return TreeNode(val)
    
    #recursive case
    elif val < curNode.val:
    	curNode.leftNode = self.__insertHelp(curNode.leftNode, val)
    elif val > curNode.val:
    	curNode.rightNode = self.__insertHelp(curNode.rightNode, val)

    return curNode

def insert(self, val):
    self.root = self.__insertHelp(self.root, val)

delete : 특정 val을 tree안에서 제거한다.

이 delete가 BST 구현에 있어 가장 어려운 파트라고 보면 된다. 작성과 함께 설명을 적어두겠다.

def __deleteHelp(self, curNode, val):
    # base case
    if not curNode:
    	return None
    
    # 값을 갖는 node 찾기
    if val < curNode.val:
    	curNode.leftNode = self.__deleteHelp(curNode.leftNode, val)
    elif val > curNode.val:
    	curNode.rightNode = self.__deleteHelp(curNode.rightNode, val)

	# 제거과정
    else:
    	    # children이 없는경우, 즉 leafNode 인 경우
        if not curNode.leftNode and not curnode.rightNode:
    	    return None
            
            # left, right 중 한 쪽 child만 있을 경우
        elif not curNode.leftNode:
            return curNode.rightNode
        elif not curNode.rightNode:
            return curNode.leftNode
            
        # child가 두 쪽 다 있을 경우, rightChild의 min 값, 혹은 leftChild의 max 값과 바꿔줘야 한다.
        else:
            # 일반적으로 rightNode의 min 값을 succesor 라고 한다.
            # (1) 여기서 rightNode에서 가장 작은 값을 구하고, 
            # (2) 그 값을 갖는 노드를 rightNode에서 제거하고
            # (3) 현재 node의 값을 succesor 값으로 바꿔주면 된다.
            succesor = self.__findMin(curNode.rightNode)
            curNode.rightNode = self.__deleteHelp(curNode.rightNode, successor)
            curNode.val = succesor
                
    return curNode
    			
# succesor를 찾기위한 function이다.
def __findMin(self, curNode):
    if not curNode.leftNode:
    	return curNode.val
    else:
    	return self.__findMin(curNode.leftNode) 
    
def delete(self, val):
	self.root = self.__deleteHelp(self.root, val)

performance

• 모든 BST Operations(search, insert, delete)의 time complexity는 O(h)이다.
• 여기서 h는 binary search tree의 height를 의미한다.

worst case

worst case의 경우에는 모든 node가 한쪽으로 쏠린 skewed 되어 있는 경우이다. 예를 들어 node가 n개인 tree의 모든 node가 left child는 없고 right child만 가진다고 생각해보자. 이 경우 tree의 height는 n이 될 것이고, 따라서 opeartion들의 time complexity는 O(n)이 된다.

best case

best case의 경우 h가 n에 비해 가장 작아질 때를 말한다. 이러한 경우는 perfect binary tree일 때 이다. 이 때는 binary search tree의 height가 logn이 되어 결국 operations의 time complexity가 O(logn)이 된다!