Programրագիր ՝ ստուգելու համար, որ երկուական ծառը BST է, թե ոչ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Adobe Amazon Բումերանգի առևտուր Փաստեր GreyOrange MakeMyTrip- ը Microsoft Պատգամախոս OYO սենյակներ Qualcomm Snapdeal VMware Walmart Labs Վուքեր
Երկուական որոնման ծառ Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«Երկուական ծառ BST- ի ստուգման ծրագիր է», - ասում է, որ ձեզ տրվում է երկուական ծառ և դուք պետք է ստուգեք, թե արդյոք երկուական ծառը բավարարում է երկուական որոնման ծառի հատկություններին: Այսպիսով, երկուական ծառն ունի հետևյալ հատկությունները. 

  1. Ձախ ենթածառը պետք է ունենա արմատից փոքր արժեք ունեցող հանգույցներ
  2. Իշտ ենթատեսակը պետք է պարունակի արմատից մեծ տվյալներ ունեցող հանգույցները
  3. Ձախ և աջ ենթատեսակները իրենք պետք է լինեն երկուական որոնման ծառ, ինչը նշանակում է, որ իրենք պետք է հետևեն երկուական որոնման ծառի հատկություններին:

Օրինակ

Մուտքային

Programրագիր ՝ ստուգելու համար, որ երկուական ծառը BST է, թե ոչ

YES

Բացատրություն. Տրված ծառը հետևում է երկուական որոնման ծառի բոլոր հատկություններին: Ձախ ենթածառի բոլոր հանգույցները ավելի փոքր են, քան արմատային արժեքը: Եվ նույնը վերաբերում է ճիշտ ենթածառին, հանգույցներն ունեն արմատից մեծ արժեք: Իսկ ձախ ենթածառը և աջը ենթաընկերությունն իրենք են հետևում BST- ի հատկություններին:

Մուտքային

NO

Բացատրություն. Treeառը չի հետևում BST- ը, որտեղ ձախ ենթածառի բոլոր հանգույցները պետք է ունենան ավելի փոքր արժեք, քան արմատը:

Appրագրի մոտեցում ՝ ստուգելու համար, որ երկուական ծառը BST է, թե ոչ

Միամիտ մոտեցում (Սխալ մոտեցում)

Այստեղ մենք պարզապես գրում ենք մի ծրագիր, որը ստուգում է ՝ արդյոք ձախ ենթածառի արմատը արժեքի փոքր է, քան արմատային արժեքը: Իսկ աջ ենթածառի արմատն ավելի մեծ արժեք ունի, քան արմատը: Դրանից հետո ռեկուրսիվորեն ստուգեք ձախ և աջ ենթատեսակների առկայությունը: Բայց այս մոտեցումը սխալ է, քանի որ թեև ձախ ենթածառի արմատը արմատից փոքր է: Ձախ ենթածառի մեջ կարող է լինել մի հանգույց, որն ավելի մեծ արժեք ունի, քան արմատը: Նմանապես ճիշտ subtree- ի համար: Այսպիսով, այդ դեպքում այս մոտեցումը ձախողվում է:

Գործարկեք ալգորիթմը տրված ծառի վրա (պատկեր): Դուք կգտնեք, թեև ալգորիթմը կվերադարձնի, որ տրված երկուական ծառը BST է: Բայց քանի որ աջ ենթածառի 1-ը 2-ից փոքր է: Այսպիսով, մենք պետք է գտնենք որևէ այլ մոտեցում:

Արդյունավետ մոտեցում (Ճիշտ մոտեցում)

Մենք կօգտագործենք նվազագույն և առավելագույն երկու փոփոխականներ `մեր ձախ և աջ ենթատեսակների տիրույթը որոշելու համար: Սա մեզ կասի, արդյոք ձախ ենթածառի տարրերը ինչ-որ միջակայքում են: Այս միջակայքը կշարունակվի փոխվել, քանի որ մենք շարունակում ենք փոխել ենթաթևերը: Այս մեթոդը պարզապես օգտագործվում է այն թերությունը վերացնելու համար, որին միամիտ մոտեցում ենք ունենում: Այնտեղ մենք չկարողացանք երաշխավորել, որ ձախ ենթածառի բոլոր տարրերը արմատից փոքր կլինեն: Եվ աջ ենթածառի բոլոր տարրերը ավելի մեծ կլինեն, քան արմատը: Սկզբնապես, մենք կկանչենք մեր BST ստուգիչը `նվազագույն սահմանվածով` որպես ամբողջ թիվի նվազագույն արժեք, իսկ առավելագույնը `որպես ամբողջի առավելագույն արժեք: Քանի որ դա այն միջակայքն է, որը պետք է բավարարի արմատային արժեքը: Այժմ մենք կթարմացնենք առավելագույնը ձախ ենթածառի համար որպես root's value-1, իսկ աջ subtree- ի համար `նվազագույն արժեքը սահմանենք որպես root- ի արժեք: Այժմ մենք կշարունակենք համապատասխանաբար սահմանել նվազագույն և առավելագույնի արժեքները և գործառույթով կանչել գործառույթը ձախ և աջ ենթածառի համար:

Կոդ

C ++ ծրագիր ՝ ստուգելու համար, որ երկուական ծառը BST է, թե ոչ

#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

Java ծրագիր ՝ ստուգելու համար, որ երկուական ծառը BST է, թե ոչ

// 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք միայն ծառի միջով ենք անցել: Եվ մեկ անցումն արժե գծային ժամանակի բարդություն:

Տիեզերական բարդություն

Ո (1) հաստատուն տարածք, քանի որ մենք օգտագործել ենք միայն հաստատուն քանակի փոփոխականներ, բայց ծրագիրն ընդհանուր առմամբ վերցնում է O (N), քանի որ ծառի մեջ կան N հանգույցներ: