올바른 이진 탐색 트리인지 확인하기

문제는 아니고 이론이다. 특정한 트리가 주어졌을 때 이 트리가 이진탐색 트리의 조건에 만족하는지 만족하지 못하는지 체크하는 문제이다. 

 

이진 탐색 트리를 만족하기 위해서는 부모의 노드 오른쪽에는 큰 값 왼쪽에는 작은 값이 위치하는 것을 체크해주면 된다. 하지만 이를 하나하나씩 다 체크해주면 확인하기에는 시간복잡도 부분에서 오래걸리게 된다. 따라서 O(n)만에 해결하는 방법을 작성해보려고 한다. 

 

우선 아래 그림을 보자 

 

해당 노드의 최대 값과 최소 값을 지정한 후 이 사이에 있다면 참이고 그 반대면 거짓이 된다. 참과 거짓을 밝히는 if문은 아래와 같다. 

if(minValue <= value && maxValue > value)
	true;
if(minValue > value || maxValue <= value )
    false;

maxValue가 작거나 같을 때 false인 이유는 위의 경우 값이 같을 때 오른쪽으로 가기 때문에 value가 minValue로 이동한다. 따라서 maxValue와 같아질 때는 없는 것이다. 

 

그래서 재귀로 생각해보면 아래와 같다.

bool check(BST* tree, int maxValue, int minValue){
	if(tree->value < minValue || tree->value >= maxValue)
      return false;
      
      if(tree->left != NULL && !check(tree->left, tree->value, minValue)){
      	return false;
      }
      
      if(tree->right != NULL && !check(tree->right, maxValue, tree->value)){
      	return false;
      }
      
      return true;
}

 

 

여기서 minValue와 maxValue는 왼쪽 노드로 이동할 때에는 value가 maxValue로 오른쪽으로 이동할 때에는 value가 minValue로 이동한다. 따라서 위와 같은 코드가 나오는 것이다.