KOOC/Linear Structure & Dynamic Programming

Binary Search Tree <6-2>

dataart 2023. 12. 29. 17:53

 

<< 6주차 Lecture Note 2번째>>

  • Binary Search Tree : a simple structure
  • Insert Operation of Binary Search Tree
  • Search Operation of Binary Search Tree

Binary Search Tree : a simple structure

이진검색트리(BST)란, degree 가 2인 Tree를 말한다.

BST의 설계 목적은 저장된 데이터를 더 빠르게 찾는 것이다.

 

 

 

위 그림에서, 링크드리스트와 BST에서 '1004'를 찾는 과정을 비교해보자.

링크드리스트는 직렬구조로 데이터를 저장하기때문에, 1004를 찾기 위해 4번에 retrieval이 발생한다.

하지만, 데이터 저장에 일정한 규칙이 있다면 BST가 훨씬 빠르다.

예를 들어 특정 노드(1003)의 왼쪽에는 항상 해당 노드보다 작은 숫자(1002),

오른쪽에는 항상 큰 숫자(1004)가 저장되는 규칙이 있다고 해보자.

 

규칙을 알고있다면, 처음 마주한 노드의 값이 1003일 경우 우리는 굳이 왼쪽 노드를 탐색할 필요 없이 오른쪽 노드만 탐색하면 된다.

이처럼 BST를 이용해 데이터를 탐색할 경우 링크드리스트보다 retrieval을 훨씬 줄일 수 있다.

 

일반적인 Tree Node를 코드로 간단하게 정의하면 아래와 같다.

class TreeNode:
    nodeLHS = None
    nodeRHS = None
    nodeParent = None
    value = None
    
    def __init__(self, value, nodeParent):
        self.value = value
        self.nodeParent = nodeParent
        
    def getLHS(self):
        return self.nodeLHS
    def getRHS(self):
        return self.nodeRHS
    def getValue(self):
        return self.value
    def getParent(self):
        return self.nodeParent
    def setLHS(self, LHS):
        self.nodeLHS = LHS
    def setRHS(self, RHS):
        self.nodeRHS = RHS
    def setValue(self, value):
        self.value = value
    def setParent(self, nodeParent):
        self.nodeParent = nodeParent

 

 

일반적인 Tree Node는 특정 노드의 왼쪽, 오른쪽, Parent 노드를 Reference로 갖는다.

위 Tree Node 클래스는 한 개의 노드에 대해 정의하는 클래스인 것이다.

 

BST의 코드는 Root만을 Reference로 갖는다.

 

class BinarySearchTree:
    root = ''
    
    def __init__(self):
        pass
    
    def insert(self, value, node=''):
        pass
    
    def search(self, value, node=''):
        pass
    
    def delete(self, value, node=''):
        pass
    
    def findMax(self, node=''):
        pass
    
    def findMin(self, node=''):
        pass
    
    def traverseLevelOrder(self):
        pass
    
    def traverseInOrder(self, node=''):
        pass
    
    def traversePreOrder(self, node=''):
        pass
    
    def traversePostOrder(self, node=''):
        pass

 

 

코드에서 보듯이, BST는 Root만 레퍼런스로 정해놓고, Root로부터 노드를 insert, delete 하는 operator를 정의한다.

 

Insert Operation of Binary Search Tree

 

이진탐색트리에서 데이터를 삽입하는 코드는 아래와 같다.

 

class BinarySearchTree:
    root = None
    
    def insert(self, value, node = None):
        if node is None:
            node = self.root
        
        if self.root == None:
            self.root = TreeNode(value, None)
            return
        
        if value == node.getValue():
            return
        
        if value > node.getValue():
            if node.getRHS() is None:
                node.setRHS(TreeNode(value, node))
            else:
                self.insert(value, node.getRHS()) # recursion
                
        if value < node.getValue():
            if node.getLHS() is None:
                node.setLHS(TreeNode(value, node))
            else:
                self.insert(value, node.getLHS()) # recursion
                
        return

 

 

특정 노드에 value를 삽입하고자 할 때 insert 메서드를 사용한다.

 

  • 만약 insert 파라미터인 node에 지정한 노드가 없다면,
    node는 자동적으로 root 노드를 지정하도록 되어 있다.
  • 만약 root 노드가 value 없이 비어있다면(None),
    insert 되는 value는 root 노드의 value가 된다.
  • 만약 insert 하려는 value와 기존 노드의 value가 갖다면,
    insert 메서드를 종료한다.
  • 만약 insert 하려는 value가 기존 노드의 value보다 크다면,
    기존 노드의 오른쪽 노드를 확인한다.
    \(\quad\) 이 때, 오른쪽 노드가 None이라면 그 노드에 value를 삽입한다.
    \(\quad\) 이 때, 오른쪽 노드가 None이 아니라면 기존 노드의 오른쪽 노드에서 다시 insert 메서드를 실행한다.
  • 만약 insert 하려는 value가 기존 노드의 value보다 다면,
    기존 노드의 왼쪽 노드를 확인한다.
    \(\quad\) 이 때, 왼쪽 노드가 None이라면 그 노드에 value를 삽입한다.
    \(\quad\) 이 때, 왼쪽 노드가 None이 아니라면 기존 노드의 왼쪽 노드에서 다시 insert 메서드를 실행한다.

Search Operation of Binary Search Tree

 

이진탐색트리 구조에서 데이터를 탐색하는 방법은 insert 메서드와 비슷한 논리를 갖는다.

아래 코드에서 정의한 search 메서드를 보자.

class BinarySearchTree:
    root = None
    
    def insert(self, value, node = None):
        if node is None:
            node = self.root
        
        if self.root == None:
            self.root = TreeNode(value, None)
            return
        
        if value == node.getValue():
            return
        
        if value > node.getValue():
            if node.getRHS() is None:
                node.setRHS(TreeNode(value, node))
            else:
                self.insert(value, node.getRHS()) # recursion
                
        if value < node.getValue():
            if node.getLHS() is None:
                node.setLHS(TreeNode(value, node))
            else:
                self.insert(value, node.getLHS()) # recursion
                
        return
                
    def search(self, value, node = None):
        if node is None:
            node = self.root
            
        if value == node.getValue():
            return True
        
        if value > node.getValue():
            if node.getRHS() is None:
                return False
            else:
                return self.search(value, node.getRHS())
        
        if value < node.getValue():
            if node.getLHS() is None:
                return False
            else:
                return self.search(value, node.getLHS())

 

 

  • 만약 search 메서드에 입력하는 파라미터 node가 지정되지 않으면,
    node는 root 노드를 가르킨다.
  • 만약 search 메서드에 입력된 파라미터 value가 node의 value와 같으면,
    True를 리턴한다.
  • 만약 value가 node의 value보다 크면,
    기존 노드의 오른쪽 노드를 확인한다.
    \(\quad\) 이 때, 오른쪽 노드 값이 없다면, False를 리턴한다.
    \(\quad\) 이 때, 오른쪽 노드 값이 있다면, 다시 오른쪽 노드에서 search 메서드를 실행한다.
  • 만약 value가 node의 value보다 작으면,
    기존 노드의 왼쪽 노드를 확인한다.
    \(\quad\) 이 때, 왼쪽 노드 값이 없다면, False를 리턴한다.
    \(\quad\) 이 때, 왼쪽 노드 값이 있다면, 다시 왼쪽 노드에서 search 메서드를 실행한다.

이런 방식으로 찾고자하는 value를 탐색하게되면, value까지 이어지는 경로 외에 존재하는 노드들은 굳이 탐색을 하지 않는다.
즉, 확인하는 노드의 수가 링크드리스트에 비해 확연히 줄어 데이터 탐색 시간을 감소시킬 수 있다.

반응형