[CLRS] [12] Binary Search Tree(BST)

1. Binary Search Tree?

- 이진 탐색(Binary Search)의 개념을 트리 형태의 구조에 점목한 자료구조

- 각 노드 키가 왼쪽 서브트리에 있는 키들보다 크고, 오른쪽 서브트리에 있는 키들보다 작다.

- 일반적으로 키값이 같은 노드는 복수로 존재하지 않아야 한다.

 

 

2. BST의 구조

- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

- 노드의 오른쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

- 루트의 왼쪽 서브트리와 오른쪽 서브트리는 BST이다.

 

3. BST CODE구현

3.1. BST에 사용되는 클래스

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.right = None
        self.left = None
        self.head = None

class BST:
    def __init__(self):
        self.root = None

 

3.2. Insert method

- BST에 새로운 노드를 삽입한다는 것은 노드를 삽입한 뒤 트리의 형태가 BST를 유지해야 한다.

 

- 노드 삽입 과정

i) 삽입위치 찾기
-- 삽입하는 키를 k라고 하자.

-- k가 루트 키 보다 작으면 왼쪽서브트리에 삽입, k가 루트 키보다 크면 오른쪽 서브트리에 삽입

-- 이과정을 서브트리에 반복하여 삽입 위치를 정함

 

ii) 새로운 노드를 삽입위치에 추가

def insert(self, key, value):
        if self.root:
            self.insert_to_subtree(key,value,self.root)
        else:
            self.root = Node(key,value)

    def insert_to_subtree(self, key, value, sroot):
        if key < sroot.key:
            if sroot.left:
                self.insert_to_subtree(self,key,value,sroot.left)
            else:
                sroot.left = Node(key,value)
                sroot.left.haed = sroot
        elif key > sroot.key:
            if sroot.right:
                self.insert_to_subtree(self,key,value,sroot.right)
            else:
                sroot.right = Node(key, value)
                sroot.right.head = sroot

 

3.3. Search method

- Insert method와 거의 유사하다.

    def search(self,key):
        return self.search_in_subtree(key,self.root)
    
    def search_in_subtree(self,key,sroot):
        
        if sroot is None:
            return None
        
        elif key == sroot.key:
            return sroot.value
        
        elif key < sroot.key:
            return self.search_in_subtree(key,sroot.left)

        else:
            return self.search_in_subtree(key, sroot.right)

 

3.4. min/max 노드 탐색

- min_node() : BST의 root노드에서 왼쪽 자식노드로 계속 내려가면 된다

- max_node() : BST의 root노드에서 오른쪽 자식노드로 계속 내려가면 된다

    def min_node(self,sroot):
        if sroot is None:
            return None
        else:
            if sroot.left:
                return self.min_node(self,sroot.left)
            else:
                return sroot
            
    def max_node(self,sroot):
        if sroot is None:
            return None
        else:
            if sroot.right:
                return self.max_node(self,sroot.right)
            else:
                return sroot

 

3.5. Delete Method

- Delete 연산은 삽입과정보다 복잡하다.

 

- 이진탐색트리의 노드 삭제는 3가지 경우를 가진다.

i) 자식 노드가 없는 노드를 삭제하는 경우

ii) 자식 노드가 1개인 노드를 삭제하는 경우

iii) 자식 노드가 2개인 노드를 삭제하는 경우

a) 삭제할 노드의 왼쪽서브트리에서 키값이 가장 큰 노드를 탐색

-- 이 노드를 왼쪽최대노드라고 하자.

b) 왼쪽최대노드의 키와 값을 삭제할 노드에 복사

-- 이때 삭제할 노드가 삭제 됨

c) 왼쪽 최대 노드를 삭제

-- 재귀적 방법으로 삭제

 

def delete(self, key: int) -> None:
        self.root = self.delete_in_subtree(key, self.root)

    def delete_in_subtree(self, key, sroot):
        if sroot is None:
            return None
        
        if key < sroot.key:
            sroot.left = self.delete_in_subtree(key,sroot.left)
    
        elif key > sroot.key:
            sroot.right = self.delete_in_subtree(key,sroot.right)

        else:
            if sroot.left and sroot.right:
                max_node = self.max_node(sroot.left)
                sroot.key  = max_node.key
                sroot.value = max_node.value

                sroot.left = self.delete_in_subtree(max_node.key,sroot.left)
            elif sroot.left:
                sroot = sroot.left
            
            elif sroot.right:
                sroot = sroot.right
            else:
                sroot = None
        return sroot

 

3.6. 전체 코드

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.right = None
        self.left = None
        self.head = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key, value):
        if self.root:
            self.insert_to_subtree(key,value,self.root)
        else:
            self.root = Node(key,value)

    def insert_to_subtree(self, key, value, sroot):
        if key < sroot.key:
            if sroot.left:
                self.insert_to_subtree(self,key,value,sroot.left)
            else:
                sroot.left = Node(key,value)
                sroot.left.haed = sroot
        elif key > sroot.key:
            if sroot.right:
                self.insert_to_subtree(self,key,value,sroot.right)
            else:
                sroot.right = Node(key, value)
                sroot.right.head = sroot
            
    def search(self,key):
        return self.search_in_subtree(key,self.root)
    
    def search_in_subtree(self,key,sroot):
        
        if sroot is None:
            return None
        
        elif key == sroot.key:
            return sroot.value
        
        elif key < sroot.key:
            return self.search_in_subtree(key,sroot.left)

        else:
            return self.search_in_subtree(key, sroot.right)
        
    def min_node(self,sroot):
        if sroot is None:
            return None
        else:
            if sroot.left:
                return self.min_node(self,sroot.left)
            else:
                return sroot
            
    def max_node(self,sroot):
        if sroot is None:
            return None
        else:
            if sroot.right:
                return self.max_node(self,sroot.right)
            else:
                return sroot
            
    def delete(self, key: int) -> None:
        self.root = self.delete_in_subtree(key, self.root)

    def delete_in_subtree(self, key, sroot):
        if sroot is None:
            return None
        
        if key < sroot.key:
            sroot.left = self.delete_in_subtree(key,sroot.left)
    
        elif key > sroot.key:
            sroot.right = self.delete_in_subtree(key,sroot.right)

        else:
            if sroot.left and sroot.right:
                max_node = self.max_node(sroot.left)
                sroot.key  = max_node.key
                sroot.value = max_node.value

                sroot.left = self.delete_in_subtree(max_node.key,sroot.left)
            elif sroot.left:
                sroot = sroot.left
            
            elif sroot.right:
                sroot = sroot.right
            else:
                sroot = None
        return sroot