공부
[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
파이썬은 정수 최소값 최대값 제한이 없나요?
자바에서는 Integer.MIN_VALUE나 Integer.MAX_VALUE로, C++에서는 <climits>로 정수 최소/최대값을 구했었는데파이썬에서도 최소값 최대값이 있는지 궁금합니다.
hashcode.co.kr
이진탐색트리 확인 알고리즘 (Binary Search Tree Verification Algorithm)
Binary Search Tree란, 검색과 삽입을 모두 O(logN) 이라는 빠른 시간 내에 수행할 수 있는 매우 효과적인 비선형 자료구조(Non-Linear Data Structure) 이다. Binary Search Tree 를 구현하는 건 어렵지않지만,..
jins-dev.tistory.com
728x90