TIL - 0123

문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업

Delete Operation and Minimum & Maximum of Binary Search Tree

Delete operation of binary search tree

1. Deleting a node with no children
2. Deleting a node with one child
3. Deleting a node with two children

Deleting a node with no children

삭제하려는 노드를 단순 삭제만 하면됨 Untitled.png)

Deleting a node with one child

삭제하려는 노드의 child node 와 parent node 를 연결

Untitled.png)

Deleting a node with two children

1. LHS 쪽에 MAX value 를 찾거나 RHS 방향의 MIN value 를 찾는다
2. 위에서 찾은 노드의 value 를 삭제하려는 노드의 value 로 복사
3. 위에서 찾은 노드를 삭제처리

   • 예시 Untitled.png)

   • RHS Untitled.png)

   • LHS Untitled.png)

Maximum of Binary Search Tree

Untitled.png)

Finding min in a BST

• LHS 를 계속해서 따라간다 → 왜냐하면 가장 작은 값은 왼쪽에 존재하기 때문, 만약 LHS 를 가지고 있지 않다면 현재 노드가 가장 작은 value 가진 노드

Finding max in a BST

• RHS 를 계속해서 따라간다 → 왜냐하면 가장 큰 값은 오른쪽에 존재하기 때문, 만약 RHS 가 없다면 현재 노드가 가장 큰 value 를 가진 노드

코드

def delete(self, value, node = None):
        if node is None:
            node = self.root
        if node.get_value() < value:
            return self.delete(value, node.get_rhs())
        if node.get_value() > value:
            return self.delete(value, node.get_lhs())
        
        if node.get_value() == value:
            # two child              
            if (node.get_lhs() is not None
                and node.get_rhs() is not None):
                min_node = self.find_min_value(node.get_rhs())
                node.set_value(min_node.get_value())
                self.delete(min_node.get_value(), node.get_rhs())
                return 
            
            parent = node.get_parent()
            
            # one child             
            if node.get_lhs() is not None:
                if node == self.root:
                    self.root = node.get_lhs()
                elif  parent.get_lhs() == node:
                    parent.set_lhs(node.get_lhs())
                    node.get_lhs().set_parent(parent)
                else:
                    parent.set_rhs(node.get_lhs())
                    node.get_lhs().set_parent(parent)
                return
            if node.get_rhs() is not None:
                if node == self.root:
                    self.root = node.get_rhs()
                elif parent.get_lhs() == node:
                    parent.set_lhs(node.get_rhs())
                    node.get_rhs().set_parent(parent)
                else:
                    parent.set_rhs(node.get_rhs())
                    node.get_rhs().set_parent(parent)
                return
            
            # no child             
            if node == self.root:
                self.root = None
            elif parent.get_lhs == node:
                parent.set_lhs(None)
            else:
                parent.set_rhs(None)
            return
    
    def find_max_value(self, node = None):
        if node is None:
            node = self.root
        if node.get_rhs() is None:
            print(node.value)
            return node
        return self.find_max_value(node.get_rhs())
    
    def find_min_value(self, node = None):
        if node is None:
            node = self.root
        if node.get_lhs() is None:
            print(node.value)
            return node
        return self.find_min_value(node.get_lhs())