Binary Search Tree, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (8)

지금까지 Linked list 및 해시 테이블까지 살펴봤습니다. Linked list는 첫 노드만 알고 있으면 해당 리스트 내 모든 노드값들을 알 수 있습니다. 

the value of first node = 1
first.next.val = 2
first.next.next.val = 3

그런데 Linked list는 search 방면에서 시간 복잡도가 무조건 $O(N)$이 걸리기 때문에 7을 찾기 위해선 전체 리스트를 쭉 훑어야 합니다. 이보다 조금 나은 성능을 보이는 것은 아래와 같이 first 노드를 기준으로 한 번은 왼쪽, 한 번은 오른쪽에 노드를 연결하는 것인데요. 이 역시 $O(N/2)$, 즉 O(N)의 시간 복잡도를 가집니다. 

그렇다면 어떻게 성능을 개선할 수 있을까요? 아래 그림과 같이 각 노드마다 왼쪽, 오른쪽 노드를 연결한다고 생각해봅시다. 의사결정트리(decision tree)를 이미 알고 계신 분은 익숙한 구조일 것입니다. 아래는 전형적인 이진트리(binary tree)의 특징입니다. 

- 맨 윗층의 노드를 루트(root)라고 부른다
- 루트 아래 노드를 잎(leaf)이라 부른다
- 각 노드는 최소 0개, 최대 2개의 노드를 가진다
- 동일한 층의 노드는 연결되지 않는다
- 각 노드(=child)는 오로지 바로 위 노드(=parent)하고만 연결된다

이진 트리 검색(Binary Search Tree)이란?

몇 가지 특성을 먼저 소개하겠습니다. 이진트리와 비교해서, 크기에 따른 정렬(ordering)이 있다는 점이 큰 차이점입니다.

- 모든 노드 x의 값은 유니크하다
- 노드 x의 왼쪽에 위치한 모든 노드 y는 x 값보다 작다
- 노드 x의 오른쪽에 위치한 모든 노드 z는 x 값보다 크다

먼저, 기본적인 트리 노드를 생성하고 search까지 구현하는 코드를 작성해보겠습니다. 

class TreeNode():
    def __init__(self, x: int) -> None:
        self.val = x
        self.left = None
        self.right = None

class BST():
    def __init__(self, root: TreeNode) -> None:
        self.root = root
    
    # __searchHelp(): 외부에서는 접근하지 못하는, 내부에서만 접근 가능한 함수
    def __searchHelp(self, curNode: TreeNode, x: int) -> TreeNode:
        # 기본 조건 
        if not curNode:
            return None
        if x == curNode.val: # 우리가 찾고자 하는 값
            return curNode
        
        # 재귀 반복 구간
        if x < curNode.val:
            return self.__searchHelp(curNode.left, x)
        else:
            return self.__searchHelp(curNode.right, x)

    def search(self, x: int) -> TreeNode:
        return self.__searchHelp(self.root, x)

이제 insert를 구현해보도록 하겠습니다. 

def __insertHelp(self, curNode: TreeNode, x: int) -> TreeNode:
        # Base case
        if not curNode: # insertion하려는 노드가 이진트리에 없는 경우 트리노드 생성
            return TreeNode(x)
        if x == curNode.val:
            return curNode

        # Recursive case
        if x < curNode.val:
            curNode.left = self.__insertHelp(curNode.left, x) # 새롭게 insert하려는 트리노드의 적절한 위치를 찾고 링크를 연결해주어야 함(curNode.left = )
        else:
            curNode.right = self.__insertHelp(curNode.right, x)
        
        return curNode

    def insert(self, x: int) -> None:
        self.root = self.__insertHelp(self.root, x) # root 노드가 없는 경우, insertion을 하면 바로 root 노드가 되게끔 
        # return self.__insertHelp(self.root, x) -> 여전히 root 노드가 없는 상황이 됨

마지막으로 delete를 구현할 차례입니다. delete는 총 3가지 케이스를 생각해 봐야 하는데요.

1. 최하위 리프 노드를 삭제할 경우
2. 자식 노드가 1개 있는 부모 노드를 삭제할 경우
3. 자식 노드가 여러 개인 부모 노드를 삭제할 경우

가장 간단한 경우는 아무래도 1번입니다. 맨 밑에 있는 리프 노드는 어떠한 자식 노드도 없기 때문에 해당 노드를 찾아서 삭제하기만 하면 됩니다.

사실 2번도 괜찮습니다. 아래 그림에서 보이듯이, 노드6을 삭제한다면 바로 아래에 있는 노드7은 할아버지(?) 노드의 자식으로 입양을 가면 됩니다. 주의해야 할 점은 노드6과 노드7 모두 노드8의 왼쪽에 위치한다는 것입니다. 어차피 노드8 보다 모두 작을 것이기 때문에 노드6이 없어져도 그 아래 자식 노드를 편하게 노드8에 연결시키면 되는 것이죠. 

3번은 조금 생각이 필요합니다. 만약 루트 노드인 4를 삭제한다고 가정해봅시다. 자식 노드들은 혼돈의 카오스가 될 수 있습니다. 누가 루트 노드 자리를 차지할 것인지 생각해야 하는데, 먼저 왼쪽 부분은 루트 노드보다 작아야 하고, 오른쪽 부분은 루트 노드보다 커야 합니다.

그럼 1) 왼쪽 부분에 있는 노드들 중 가장 큰 값을 루트 노드로 위치시키거나, 2) 오른쪽 부분에 있는 노드들 중 가장 작은 값을 루트 노드로 위치시키는 방법은 어떨까요? 아래 노란색으로 칠해진 노드를 예로 들면, 노드3이 루트 노드로 와도 여전히 이진 검색 트리 형태를 유지하죠. 노드6이 루트 노드로 와도 여전히 유지됩니다. 둘 중 어느 것이나 선택해도 됩니다. 

이때 노드3을 루트 노드로 올리든, 노드6을 루트 노드로 올리든 먼저 해당 노드를 삭제하고 올리는 과정을 거칩니다. 따라서 노드3의 경우, 1번 케이스를 먼저 하게 될 것이고, 노드6의 경우 2번 케이스를 먼저 하게 될 것입니다. 

이진 검색 트리의 시간 복잡도는 "균형"을 이룰 때 $O(logN)$입니다. 균형을 이루지 않는 경우는 어떻게 될까요? 이진 검색 트리 형태는 맞는데, 각 노드가 하나의 자식 노드만 가질 경우겠죠. 아래처럼 이진 검색 트리가 생성되면 시간 복잡도는 결국 $O(N)$이 됩니다. 

물론, 어떻게 균형 잡힌 이진 검색 트리 구조를 만들 것인지 연구하는 방법도 있습니다만 거기까지는 다루지 않겠습니다. 이후에 심화 과정으로 나아간다면 설명드리겠습니다.

delete까지 구현한 코드입니다. 여전히 재귀 구조가 파악하기 힘들어 작동 과정을 그림으로 표현해봤습니다. 다른 분들도 참고하시면 좋겠습니다.

def __findMax(self, curNode: TreeNode) -> int:
        # Base case
        if not curNode.right: # 내 오른쪽에 아무것도 없을 경우, 내가 가장 큰 노드임
            return curNode.val
        # Recursive case
        else: 
            return self.__findMax(curNode.right)

    def __deleteHelp(self, curNode: TreeNode, x: int) -> TreeNode:
        if not curNode: # 기준이 되는 노드(=root node)가 없는 경우 진행 불가
            return None
        
        # Recursive case
        if x < curNode.val:
            curNode.left = self.__deleteHelp(curNode.left, x) # x를 찾아서 지우고, x가 리턴하는 노드(None or 자식 노드)를 현재 노드의 left 노드로 링크 걸기
        elif x > curNode.val:
            curNode.right = self.__deleteHelp(curNode.right, x)

        else: # x == curNode.val: we should delete this model
            # 1. 자식 노드 없음
            if curNode.left == None and curNode.right == None:
                return None # 바로 삭제

            # 2. 자식 노드 1개
            elif curNode.left == None and curNode.right:
                return curNode.right # 지우려는 노드의 오른쪽 자식 노드 리턴 -> 할아버지 노드에 연결
            elif curNode.left and curNode.right == None:
                return curNode.left

            # 3. 자식 노드 2개 이상
            else:
                leftLargest = self.__findMax(curNode.left)
                curNode.left = self.__deleteHelp(curNode.left, leftLargest) # 1.왼쪽 부분에서 가장 큰 노드를 지우고, 현재 노드의 왼쪽 자식 노드로 링크 걸기
                curNode.val = leftLargest # 2. 

        return curNode # 삭제될 노드는 삭제된 최종 버전의 이진 트리 리턴
        
    def delete(self, x: int) -> None:
        self.root = self.__deleteHelp(self.root, x)

<자식 노드가 2개 이상인 경우>

- 재귀 구조가 나오면 재귀 반복문을 먼저 실행한다
- curNode.left = 재귀 반복 함수 -> 재귀 반복 함수에서 return에 해당하는 값이 curNode.left가 된다
- 재귀 반복문이 모두 끝나면 다음 줄에 있는 curNode.val = leftLargest 와 return curNode가 실행된다
- 따라서 curNode의 최종 모습은 모든 재귀 반복문이 끝난 후의 결과이다