주어진 트리가 이분 탐색 트리인지 결정하는 알고리즘

이 기사는 무엇입니까?

입력으로서 트리 구조가 건네졌을 때, 그것이 이분 탐색 트리인지 어떤지를 조사하는 알고리즘에 대해 소개한다.

이분 탐색 나무

이진 탐색 트리는 이분 나무 이며, 절의 좌측의 아이에는 절과 같거나 작은 요소 밖에 포함하지 않고, 오른쪽의 아이에는 절과 같거나 큰 요소 밖에 포함하는 것을 가리킨다.

다음 나무는 이분 탐색 나무의 보기이다.



모든 부분 트리에서 좌측의 아이가 절과 같거나 그보다 작고, 오른쪽의 아이가 절과 같거나 그것보다 큰 요소를 가지고 있다.

이진 탐색 트리인지 여부를 결정하는 알고리즘

이진 탐색 트리의 자식 절이 취할 수있는 값의 폭은 부모의 절보다 좁습니다. 위의 이분 탐색 트리를 예로 생각하자.

뿌리의 요소가 취할 수 있는 값의 폭은 [-∞, ∞] 이다. 즉, 어떠한 값이라도 문제가 없다. 루트에서 왼쪽 자식 인 7 절이 취할 수있는 값은 [-∞, 19]입니다. 왜냐하면 뿌리의 왼쪽 자식은 뿌리보다 큰 값이어서는 안됩니다. 그런 다음 7 절의 오른쪽 자식에 대해 생각합시다. 이 절의 가능한 값은 [7, 19]이고 실제 값은 11입니다. 부모가 7이므로 오른쪽의 자식은 7보다 큰 값이어야 하며 부모가 19보다 작다는 제약을 가지고 있기 때문에 이 절도 같은 제약을 인계하기 때문이다.

이와 같이, 뿌리로부터 잎을 향해 취할 수 있는 값의 레인지를 갱신하면서, 실제의 값이 그 레인지에 머무르고 있는지 어떤지를 조사하는 것으로, 주어진 트리가 이분 탐색 트리인지를 판정할 수 있다.

구체적인 구현은 다음과 같다.

# 木のノードは BstNode クラスで表現する
class BstNode:
    def __init__(self, data=None, left=None, right=None):
        self.data, self.left, self.right = data, left, right


def is_binary_tree_bst(tree: BstNode, low_range=float('-inf'), high_range=float('inf')) -> bool:
    if not tree:
        return True

    if not (low_range <= tree.data <= high_range):
        return False

    return \
        is_binary_tree_bst(tree=tree.left, low_range=low_range, high_range=tree.data) and \
        is_binary_tree_bst(tree=tree.right, low_range=tree.data, high_range=high_range)

루트로부터 재귀적으로 좌우의 아이의 부분 트리를 탐색해, 모든 절의 값이 레인지의 범위내에 가만 있으면 is_binary_tree_bst True 를 돌려준다.