DFS (스택)와 BFS (큐) 로 풀어보는 BST

BST

BST는 node.left.data <= node.data <= node.right.data 라는 규칙(invariant)를 가지는 tree로서 그 규칙 덕분에 이진탐색(binary search)의 효과를 낼 수 있게 된다.

BST의 각 노드는 다음 클래스로 정의 후 객체를 만들어서, root 노드에서부터 계속 추가하여 트리를 구성해 나갈 수 있다.

class BSTNode:
    def __init__(self, val=None, left=None, right=None)
        self.val, self.left, self.right = val, left, right

그런데 위 규칙만으로는, 삽입되는 key의 순서가 오름차순일때, 경사이진트리를 구성할 수 밖에 없어 탐색시간이 O(n)으로 늘어나게 된다. 그러므로 최대한 좌, 우 트리의 높이(height)가 균형되게 하는(balanced, 최대 차이 1) 트리 구성이 복잡도 측면에서 유리하다(삽입, 삭제, 검색 등에 O(nlgn) 보장). 이 경우 활용되는 것이 Red Blck tree나 AVL tree 등이다. 이를 위해서는 조금 더 복잡한 구현을 해야 한다.

bintrees module 

균형트리를 직접 구현하지 않고도 사용할 수 있도록 하기 위해 bintrees module이 공개되어 있다. 다음에 bintrees 활용 예시를 소개한다. sortedcontainers 모듈은 삽입과 삭제의 복잡도가 O(sqrt(n))으로 더 유리하다.

>>> t = bintrees.RBTree([(3, 'Ryan'), (2, 'Muzi'), (5, 'Jay-Z'), (1, 'Chunshik')]) 
>>> t[2]
'Muzi'
>>> t.min_item()
(1, 'Chunshik')
>>> t.max_item()
(5, 'Jay-Z')
>>> t.insert(8, 'Pengsoo')
>>> t
RBTree({1: 'Chunshik', 2: 'Muzi', 3: 'Ryan', 5: 'Jay-Z', 8: 'Pengsoo'})
>>> t.discard(5)
>>> a = t.pop_min()
>>> a
(1, 'Chunshik')
>>> b = t.pop_max()
>>> b
(8, 'Pengsoo')
>>> t 
RBTree({2: 'Muzi', 3: 'Ryan'})

 

문제 1: BST 탐색

간단한 문제를 살펴본다. https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

 

트리의 기본은 탐색이라고 할 수 있다. 문제를 간단하게 풀기 위해 재귀를 활용하여 풀어보았다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        return (root if root is None or root.val == val    # SAME AS: if not root ...
                else self.searchBST(root.left, val) if val < root.val
                else self.searchBST(root.right, val))

 

root가 비어있다면 그 자체를 돌려준다(if not root으로 해도 된다). 또는 root의 key 값(.val)이 찾아야 하는 값과 같아도 역시 root을 돌려준다. 나머지 경우, 즉, val < root.val 일 경우나 root.val < val 일 경우는 BST invariant에 따라 각각 이미 클래스 Solution 안에 정의된 함수인 self.searchBST 자신을 호출하되 전자의 경우는 왼쪽을 탐색해야 하므로 인수(argument)를 root.left로 주고 후자의 경우는 오른쪽 탐색을 위해 root.right로 준다. 찾을 값인 val은 재귀시에도 변화가 없다.

그러면 이와 같은 재귀호출을 받은 함수는 (예를 들어 왼쪽 자식트리를 인자로 받은 함수) 다시 root 자리에 root.left가 입력된 채 함수를 실행하게 된다. 이런 과정을 좌, 우측 계속하다가 보면 어느 순간 return에서 씌어진 맨 윗 줄인 root.val == val 인 경우를 만나게 되고, 그러면 그 node를 돌려준다. 그리고 이것은 다시 호출한 함수에서 return 을 바로 만나게 되므로 (return ... else self.searchBST(...)) 최종적으로 값을 돌려주게 된다.

 

문제 2: BST 검증

Validate Binary Search Tree - LeetCode

Validate Binary Search Tree - LeetCode

주어진 이진트리가 BST invariant를 만족하는지를 검증하는 문제이다.

방법1. brute force

모든 노드에 대해 좌, 우 자식 트리들이 BST를 만족하는지를 살펴보는 것이다. 먼저 왼쪽 자식 트리(left subtree)의 최대키 값(node.left.val)을 찾아 이것이 부모 노드의 키 값(node.val)보다 작거나 같은지를 살피고, 오른쪽도 마찬가지로 한다. 자식트리의 최대값을 찾는 행동을 위해서는 이것이 어떤 트리인지 모르기 때문에 모든 하위 원소를 찾아야 하니 O(n) 탐색이 필요하고 이것을 모든 노드에 대해 수행해야 하니(n) 시간복잡도는 O(n**2) 이다.

방법2. DFS (depth-first search, 깊이우선 탐색), recursion, stack

위의 방법보다 탐색 수를 적게 하는 방법은 재귀를 활용하면 가능하다. 문제를 다음 그림처럼 가장 작은 부분 형태로 줄여보자.

BST의 예

결국 BST 규칙(invariant)는 부모 노드가 그리고 각 자식 노드가 모두 BST 성질을 만족해야 한다. 그러므로 우리도 세 가지 경우를 재귀식에 담아야 한다.

부모 노드를 검증하려면 어떻게 할까. 우선, 15가 트리의 root 라고 할 때 이 노드가 취할 수 있는 값에는 제약이 없다. 여기서 '취할 수 있는 값'의 범위를 lower bound 와 upper bound로 표현하면 [-inf, inf] 가 된다. 그리고 15는 이 범위에 들어오므로 규칙을 어기지 않았다. 하지만 우리는 아직 자식 트리가 BST를 충족하는지를 알지 못하므로 여기서 BST를 충족한다(True)고 표현할 수는 없고 그저 root에서 False라고 말하지는 않고 자식노드에 대한 검증을 실시하기 위해 재귀(recurse) 한다.

왼쪽 자식트리를 검증하기 위해 키값이 7인 노드를 보자. 이 노드는 자식트리의 root가 되며, 그것의 자식트리/노드는 모두 None이다. 7은 BST 규칙을 충족할까. 여기서 충족해야 할 규칙은 부모 root (15)가 가졌던 가능 범위인 [-inf, inf]를 상속하되 다만 자식노드가 부모노드보다는 작거나 같아야 하므로 상한을 15로 바꿔야 한다: [-inf, 15]. 그리고, 7은 이 범위에 들어가므로 False라고 하지는 않겠다. 그러면 자식노드를 또 탐색해야 한다. 좌, 우측 자식노드는 None이다. 이것의 값이 없으므로 우리는 이 부분을 검증할 필요가 없이, 부모의 노드에 따라 그 서브트리의 명운이 갈리게 된다. 즉,

부모 and 좌측 자식 and 우측 자식 = 부모(T/F) = 부모(T/F) and 좌(T) and 우(T) 로 식을 세워볼 수 있다.

그래서, 재귀받은 자신이 None이면 True를 돌려준다. 이를 정리하면 다음 코드를 쓸 수 있다.

def isBSTvalid(node, lb=float('-inf'), ub=float('inf')):
    if not node:
        return True
    elif not lb <= node.val <= ub:
        return False
    else:
        return isBSTvalid(node.left, lb, node.val) and
               isBSTvalid(node.right, node.val, ub)

시간복잡도는 O(n), 공간복잡도는 O(h) 이다 (h: 트리의 높이). 먼저 루트부터 한쪽 경로를 끝까지 다 탐색한 다음, 다시 다른 경로를 끝까지 탐색한다. 만일 루트 중 왼쪽 끝부분에 BST violation이 있다면 거기까지 탐색을 다 해야 하므로 BFS와 효율성에 있어 별반 차이가 없을 것이나, 만일 root의 바로 우측 자식 노드에서 BST violation이 있다면 BFS가 DFS 대비 더 빨리 이를 발견할 수 있었으므로 더 효율적일 것이다.

다만, 위 코드를 그대로 leetcode 답으로 쓸 수는 없다. 해당 문제에서는 BST invariant를 node.left.val < node.val< node.right.val 로 정하고 있기 때문이며, class 안에 기술하도록 되어 있다. 이를 고려해서 코드를 수정하는 것은 독자에게 맡긴다(hint: self). 이렇듯 실무나 문제풀이에서 많이 쓰이는 클래스에 대해서는 추후 포스트에 적어보도록 하겠다.

방법2. BFS (breadth-first search, 너비우선 탐색), queue

먼저 틀린 코드를 붙여놓겠다.

def isBSTvalid(tree) -> bool:
    Node = collections.namedtuple('Node', ('tree', 'lb', 'ub'))
    queue = collections.deque([Node(tree, float('-inf'), float('inf'))])
    while queue:
        node = queue.popleft()
        if not node.tree: return True  # wrong
        if not node.lb <= node.tree.data <= node.ub: return False
        queue += [Node(node.tree.left, node.lb, node.tree.data),
                  Node(node.tree.right, node.tree.data, node.ub)]

이 코드는 잘못된 결과를 낸다. 왜냐면 6줄 (wrong) 에서처럼, node를 popleft 했는데 None인 경우 즉시 이 정보만 가지고 True라고 보고하기 때문이다. queue는 recursion이 아니라서, 위의 stack의 경우처럼 좌,우 서브트리로부터의 결과를 모두 and 하여 결론을 내는 것이 아니라서 바로 node.tree is None 조건만 가지고 True를 돌려버리면 자신과 sibling 관계에 있는 서브트리가 BST를 만족하는지 여부와 상관없이 True라고 판정하는 것이 되기 때문이다. 그러므로 위 코드는 아래와 같이 고쳐야 한다.

def isBSTvalid(tree):
    Node = collections.namedtuple('Node', ('tree', 'lb', 'ub'))
    queue = collections.deque([Node(tree, float('-inf'), float('inf'))])
    while queue:
        node = queue.popleft()
        if node.tree:
            if not node.lb <= node.tree.data <= node.ub:
                return False
            queue += [Node(node.tree.left, node.lb, node.tree.data),
                    Node(node.tree.right, node.tree.data, node.ub)]
    return True

즉, None인 노드가 push 되는 것은 상관없지만 그것을 popleft 했을 때는 판정 등 아무것도 실행하지 않는다. 즉, 나 자신이 None이라는 것은 결론에 아무런 영향을 주지 않는 것이다. 그저 나 자신이 key 값을 가지는 node인 경우에 이것이 적절한 범위를 갖는지만 판정하고 만일 그것이 틀리면 False 라고 리턴하고 프로그램을 종료한다. 이 경우는 recursion이 아니므로 자신을 호출한 함수가 판정결과를 가져가지 않는다. 한 노드라도 BST invariant를 어기면 즉시 전체 프로그램이 False를 리턴하고 종료되는 것이다.

그러나, None 노드까지 포함하여 모든 노드를 돌았는데도(O(n)) False가 나오지 않았다면 프로그램은 마지막 줄 처럼 True를 리턴하고 종료해야 한다.