바이너리 트리가 BST인지 확인하는 프로그램


난이도 쉽게
자주 묻는 질문 수행자 어도비 벽돌 아마존 부메랑 커머스 팩트 셋 그레이 오렌지 MakeMyTrip Microsoft 신탁 오요 룸 퀄컴 스냅 딜 VM웨어 월마트 연구소 우커
이진 검색 트리 이진 트리 나무

문제 정책

“바이너리 트리가 BST인지 확인하는 프로그램”은 바이너리 트리를 부여 받았으며 바이너리 트리가 바이너리 검색 트리의 속성을 만족하는지 확인해야한다고 말합니다. 따라서 이진 트리에는 다음과 같은 속성이 있습니다. 

  1. 왼쪽 하위 트리에는 루트보다 값이 작은 노드가 있어야합니다.
  2. 오른쪽 하위 트리에는 루트보다 큰 데이터가있는 노드가 포함되어야합니다.
  3. 왼쪽 및 오른쪽 하위 트리 자체는 이진 검색 트리 여야합니다. 즉, 이진 검색 트리의 속성을 따라야합니다.

입력

바이너리 트리가 BST인지 확인하는 프로그램

YES

설명 : 주어진 트리는 이진 검색 트리의 모든 속성을 따릅니다. 왼쪽 하위 트리의 모든 노드는 루트 값보다 작습니다. 오른쪽 하위 트리도 마찬가지입니다. 노드의 값은 루트보다 큽니다. 그리고 왼쪽 하위 트리와 오른쪽 하위 트리 자체는 BST의 속성을 따릅니다.

입력

NO

설명 : 트리는 다음 속성을 따르지 않습니다. BST여기서 왼쪽 하위 트리의 모든 노드는 루트보다 작은 값을 가져야합니다.

이진 트리가 BST인지 여부를 확인하는 프로그램 접근 방식

순진한 접근 (잘못된 접근)

여기서 우리는 왼쪽 서브 트리의 루트가 루트 값보다 작은 값을 가지고 있는지 확인하는 프로그램을 작성합니다. 그리고 오른쪽 하위 트리의 루트는 루트보다 큰 값을 갖습니다. 그런 다음 왼쪽 및 오른쪽 하위 트리를 재귀 적으로 확인합니다. 그러나이 방법은 왼쪽 하위 트리 루트가 루트보다 작기 때문에 잘못되었습니다. 왼쪽 하위 트리에 루트에 비해 더 큰 값을 가진 일부 노드가있을 수 있습니다. 오른쪽 하위 트리도 마찬가지입니다. 따라서이 경우이 접근 방식은 실패합니다.

주어진 트리 (이미지)에서 알고리즘을 실행합니다. 알고리즘이 주어진 이진 트리가 BST임을 반환하더라도 알 수 있습니다. 그러나 오른쪽 하위 트리의 1이 2보다 작기 때문에 다른 방법을 찾아야합니다.

효율적인 접근 (올바른 접근 방식)

왼쪽 및 오른쪽 하위 트리의 범위를 정의하기 위해 최소 및 최대 두 개의 변수를 사용합니다. 이것은 왼쪽 하위 트리의 요소가 특정 범위에 있는지 여부를 알려줍니다. 이 범위는 하위 트리를 계속 변경함에 따라 계속 변경됩니다. 이 방법은 순진한 접근 방식에서 직면하는 결함을 제거하는 데 사용됩니다. 왼쪽 하위 트리의 모든 요소가 루트보다 작다는 것을 보장 할 수 없습니다. 그리고 오른쪽 하위 트리의 모든 요소는 루트보다 큽니다. 처음에는 최소값을 정수의 최소값으로, 최대 값을 정수의 최대 값으로 설정 한 BST 검사기를 호출합니다. 그것이 루트의 값을 만족해야하는 범위이기 때문입니다. 이제 왼쪽 하위 트리의 최대 값을 루트의 값 -1로 업데이트하고 오른쪽 하위 트리의 경우 최소값을 루트의 값으로 설정합니다. 이제 최소 및 최대 값을 적절하게 설정하고 왼쪽 및 오른쪽 하위 트리에 대한 함수를 반복적으로 호출합니다.

암호

바이너리 트리가 BST인지 확인하는 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
} ;

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}

bool isThisBST(node* root, int minimum, int maximum)
{
    // if there is no tree
    if(!root)
        return true;

    // the root should be in the range defined by [minimum, maximum]
    if(root->data < minimum || root->data > maximum)
        return false;
    // if the root satisfies the value then we recursively check the same for left and right subtree
    // we set the minimum and maximum for left and right subtrees accordingly.
    return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}

int main()
{
    node *root = create(2);
    root->left = create(1);
    root->right = create(4);
    root->right->left = create(3);
    root->right->right = create(5);

    bool isBST = isThisBST(root, INT_MIN, INT_MAX);
    cout<<((isBST == true) ? "YES" : "NO");
    return 0;
}
YES

바이너리 트리가 BST인지 확인하는 Java 프로그램

// Class that denote a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
} 

class Tree 
{ 
    static Node root; 
  
  // return true if the tree is BST else return false
    static boolean isThisBST(Node root, int minimum, int maximum)
    { 
        // if there is no tree
      if(root == null)
          return true;
  
      // the root should be in the range defined by [minimum, maximum]
      if(root.data < minimum || root.data > maximum)
          return false;
      // if the root satisfies the value then we recursively check the same for left and right subtree
      // we set the minimum and maximum for left and right subtrees accordingly.
      return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new Node(2); 
        tree.root.left = new Node(1); 
        tree.root.right = new Node(4); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(5); 
  
        boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    	System.out.print((isBST == true) ? "YES" : "NO");
    }
}
YES

복잡성 분석

시간 복잡성

의 위에), 우리는 나무를 통해서만 횡단했기 때문입니다. 그리고 단일 순회는 선형 시간 복잡성을 필요로합니다.

공간 복잡성

O (1) 일정한 수의 변수 만 사용했기 때문에 상수 공간이지만 트리에 N 개의 노드가 있기 때문에 프로그램 전체는 O (N)을 사용합니다.