티스토리 뷰

공부

[Algorithm] Binary Search Tree Check

승가비 2022. 9. 19. 21:39
728x90
class Node:
    def __init__(self, n, left=None, right=None):
        self.n = n
        self.left = left
        self.right = right
    
    def check_left(self, min_, max_):
        return self.left is None or (min_ <= self.left.n and self.left.n <= max_)
    
    def check_right(self, min_, max_):
        return self.right is None or (min_ <= self.right.n and self.right.n <= max_)
        
def check(node):
    return _check(node) == 0
    
    
def _check(node, min_=-float('inf'), max_=float('inf')):
    if node is None:
        return 0
        
    if node.check_left(min_, min(max_, node.n)) and node.check_right(max(min_, node.n), max_):
        return _check(node.left, min_, min(max_, node.n)) + _check(node.right, max(min_, node.n), max_)
    else:
        return 1
        

t1 = Node(
    4,
    Node(2, Node(1), Node(3)),
    Node(6, Node(5), Node(7))
)


t2 = Node(
    4,
    Node(6, Node(1), Node(3)),
    Node(6, Node(5), Node(7))
)

t3 = Node(
    4,
    Node(2, Node(1), Node(3)),
    Node(6, Node(5), Node(7))
)

print(check(t1))
print(check(t2))
print(check(t3))

https://www.techiedelight.com/ko/determine-given-binary-tree-is-a-bst-or-not/

 

주어진 이진 트리가 BST인지 여부 확인

주어진 이진 트리가 BST인지 여부를 판별하십시오. 이 문제를 연습 이 문제에는 간단한 재귀 솔루션이 있습니다. BST 속성 "오른쪽 하위 트리의 모든 노드는 현재 노드보다 커야 하고 왼쪽 하위 트

www.techiedelight.com

https://hashcode.co.kr/questions/1092/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%80-%EC%A0%95%EC%88%98-%EC%B5%9C%EC%86%8C%EA%B0%92-%EC%B5%9C%EB%8C%80%EA%B0%92-%EC%A0%9C%ED%95%9C%EC%9D%B4-%EC%97%86%EB%82%98%EC%9A%94

 

파이썬은 정수 최소값 최대값 제한이 없나요?

자바에서는 Integer.MIN_VALUE나 Integer.MAX_VALUE로, C++에서는 <climits>로 정수 최소/최대값을 구했었는데파이썬에서도 최소값 최대값이 있는지 궁금합니다.

hashcode.co.kr

https://jins-dev.tistory.com/entry/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC-%ED%99%95%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Binary-Search-Tree-Verification-Algorithm

 

이진탐색트리 확인 알고리즘 (Binary Search Tree Verification Algorithm)

Binary Search Tree란, 검색과 삽입을 모두 O(logN) 이라는 빠른 시간 내에 수행할 수 있는 매우 효과적인 비선형 자료구조(Non-Linear Data Structure) 이다. Binary Search Tree 를 구현하는 건 어렵지않지만,..

jins-dev.tistory.com

 

728x90
댓글
댓글쓰기 폼