algorithm
트리가 BST인지 확인하십시오.

주어진 입력 트리가 이진 검색 트리 속성을 따르는 지 여부

예를 들어

입력이 다음의 경우 :

출력은 false 여야합니다.

왼쪽 하위 트리의 4가 루트 값 (3)보다 큽니다.

입력 내용 :

출력은 true 여야합니다.

주어진 이진 트리가 BST인지 확인하는 알고리즘

이진 트리는 다음 조건 중 하나를 만족하면 BST입니다.

1. 비어있다.
2. 하위 트리가 없습니다.
3. 트리의 모든 노드 x에 대해 왼쪽 하위 트리의 모든 키 (있는 경우)는 키 (x)보다 작아야하며 오른쪽 하위 트리의 모든 키 (있는 경우)는 키 (x)보다 커야합니다.

따라서 간단한 재귀 알고리즘은 다음과 같습니다.

is_BST(root):
  if root == NULL:
   return true

  // Check values in left subtree
  if root->left != NULL:
    max_key_in_left = find_max_key(root->left)
    if max_key_in_left > root->key:
        return false

  // Check values in right subtree
  if root->right != NULL:
    min_key_in_right = find_min_key(root->right)
    if min_key_in_right < root->key:
        return false

  return is_BST(root->left) && is_BST(root->right)

위의 재귀 알고리즘은 정확하지만 비효율적입니다. 왜냐하면 각 노드를 여러 번 통과하기 때문입니다.

각 노드의 다중 방문을 최소화하는 또 다른 방법은 방문하는 하위 트리에서 키의 최소 및 최대 값을 기억하는 것입니다. 어떤 키의 가능한 최소값을 K_MIN , 최대 값을 K_MAX 로 K_MAX . 트리 루트에서 시작하면 트리의 값 범위는 [K_MIN,K_MAX] 입니다. 루트 노드의 키를 x 합시다. 그러면 왼쪽 하위 트리의 값 범위는 [K_MIN,x) 이고 오른쪽 하위 트리의 값 범위는 (x,K_MAX] 입니다.이 아이디어를 사용하여보다 효율적인 알고리즘을 개발합니다.

is_BST(root, min, max):
    if root == NULL:
        return true

    // is the current node key out of range?
    if root->key < min || root->key > max:
        return false

    // check if left and right subtree is BST
    return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)

처음에는 다음과 같이 호출됩니다.

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

또 다른 접근법은 이진 트리의 inorder traversal을 수행하는 것입니다. inorder traversal이 정렬 된 키 시퀀스를 생성하면 주어진 트리는 BST입니다. 순서 순서가 정렬되어 있는지 확인하려면 이전에 방문한 노드의 값을 기억하고 현재 노드와 비교합니다.