Програма за проверка дали двоичното дърво е BST или не


Ниво на трудност Лесно
Често задавани в Аколит Кирпич Амазонка Бумеранг търговия FactSet GreyOrange MakeMyTrip Microsoft Оракул OYO Стаи Qualcomm Snapdeal VMware Walmart Labs Уукър
Двоично дърво за търсене Двоично дърво Дърво

Декларация за проблема

„Програма за проверка дали бинарното дърво е BST или не“ заявява, че ви е дадено двоично дърво и трябва да проверите дали бинарното дърво отговаря на свойствата на бинарното дърво за търсене. И така, двоичното дърво има следните свойства: 

  1. Лявото поддърво трябва да има възли със стойност, по-малка от основната
  2. Правото поддърво трябва да съдържа възлите с данни, по-големи от root
  3. Самото ляво и дясно поддърво трябва да бъде бинарно дърво за търсене, което означава, че те самите трябва да следват свойствата на бинарното дърво за търсене.

Пример

Вход

Програма за проверка дали двоичното дърво е BST или не

YES

Обяснение: Даденото дърво следва всички свойства на бинарно дърво за търсене. Всички възли в лявото поддърво са по-малки от стойността на корена. И същото важи и за дясното поддърво, възлите имат стойност по-голяма от root. А лявото и дясното поддърво сами следват свойствата на BST.

Вход

NO

Обяснение: Дървото не следва свойството на BST, където всички възли в лявото поддърво трябва да имат по-малка стойност от root.

Подход за програма, която да провери дали двоичното дърво е BST или не

Наивен подход (Грешен подход)

Тук просто пишем програма, която проверява дали коренът на лявото поддърво има стойност по-малка от стойността на корена. И коренът на дясното поддърво има по-голяма стойност от корен. След това рекурсивно проверете за ляво и дясно поддървета. Но този подход е погрешен, тъй като въпреки че левият корен на поддървото е по-малък от корен. Възможно е да има някакъв възел в лявото поддърво, който има по-голяма стойност в сравнение с корена. По същия начин за дясното поддърво. Така че, в този случай този подход се проваля.

Изпълнете алгоритъма на даденото дърво (изображение). Ще откриете, въпреки че алгоритъмът ще върне, че даденото двоично дърво е BST. Но тъй като 1 в дясното поддърво е по-малко от 2. И така, трябва да намерим друг подход.

Ефективен подход (Правилен подход)

Ще използваме две променливи минимум и максимум, за да определим обхвата на нашите ляво и дясно поддървета. Това ще ни каже дали елементите в лявото поддърво лежат в някакъв диапазон. Този диапазон ще продължи да се променя, както ние продължаваме да променяме поддърветата. Този метод се използва просто за отстраняване на недостатъка, пред който сме изправени при наивен подход. Там не успяхме да гарантираме, че всички елементи в лявото поддърво ще бъдат по-малки от root. И всички елементи в дясното поддърво ще бъдат по-големи от root. Първоначално ще извикаме нашата BST проверка с минималната стойност като минимална стойност на цяло число и максимална като максимална стойност на цялото число. Защото това е обхватът, който трябва да задоволи стойността на корена. Сега ще актуализираме максимума за лявото поддърво като стойност на корен-1, а за дясното поддърво зададем минималната стойност като стойност на корен. Сега ще продължим да задаваме по подходящ начин стойностите на минимум и максимум и рекурсивно извикваме функцията за ляво и дясно поддърво.

код

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

Анализ на сложността

Сложност във времето

НА), тъй като сме преминали само през дървото. И едно обхождане струва линейна сложност във времето.

Сложност на пространството

O (1) постоянно пространство, защото използвахме само постоянен брой променливи, но програмата като цяло взема O (N), защото в дървото има N възли.