برنامه ای برای بررسی اینکه درخت باینری BST است یا خیر


سطح دشواری ساده
اغلب در همبستگی خشت آمازون تجارت بومرنگ واقعیت خاکستری نارنجی MakeMyTrip مایکروسافت وحی اتاق های OYO سامسونگ اسنپدل آموزش VMware آزمایشگاه های والمارت ووکر
درخت جستجوی دودویی درخت باینری درخت

بیان مسأله

"برنامه ای برای بررسی اینکه Bary Bree یک درخت است یا نه" بیان می کند که یک درخت باینری به شما داده شده است و شما باید بررسی کنید که آیا درخت باینری از خواص درخت جستجوی باینری برخوردار است یا خیر. بنابراین ، درخت باینری دارای ویژگی های زیر است: 

  1. زیرشاخه سمت چپ باید گره هایی داشته باشد که مقداری کمتر از ریشه داشته باشند
  2. زیر درخت راست باید شامل گره هایی باشد که داده هایی بیشتر از root داشته باشند
  3. زیرشاخه چپ و راست خود باید یک درخت جستجوی دودویی باشد به این معنی که خود آنها باید از خواص درخت جستجوی دودویی پیروی کنند.

مثال

ورودی

برنامه ای برای بررسی اینکه درخت باینری BST است یا خیر

YES

توضیح: درخت داده شده از تمام خصوصیات یک درخت جستجوی دودویی پیروی می کند. تمام گره های موجود در زیر درخت سمت چپ کوچکتر از مقدار ریشه هستند. و همین امر برای زیر درخت راست نیز صادق است ، گره ها مقداری بیشتر از root دارند. و زیرشاخه چپ و زیر شاخه راست از خواص BST پیروی می کنند.

ورودی

NO

توضیح: درخت از خاصیت پیروی نمی کند BST، جایی که همه گره ها در زیر درخت سمت چپ باید مقدار کمتری نسبت به root داشته باشند.

رویکرد به یک برنامه برای بررسی اینکه آیا یک درخت باینری BST است یا خیر

رویکرد ساده لوحانه (رویکرد غلط)

در اینجا ما به سادگی برنامه ای می نویسیم که بررسی می کند آیا ریشه subtree سمت چپ مقدار کوچکتر از مقدار root دارد. و ریشه زیر درخت راست ارزش بیشتری نسبت به ریشه دارد. سپس به صورت بازگشتی شاخه های فرعی چپ و راست را بررسی کنید. اما این روش اشتباه است زیرا حتی اگر ریشه زیر درخت چپ کوچکتر از ریشه باشد. ممکن است گره هایی در زیر درخت چپ وجود داشته باشد که در مقایسه با ریشه مقدار بیشتری دارد. به طور مشابه برای زیر درخت مناسب. بنابراین ، در این صورت ، این روش شکست می خورد.

الگوریتم را روی درخت داده شده اجرا کنید (تصویر). حتی اگر الگوریتم بازگردد خواهید فهمید که درخت باینری داده شده BST است. اما از آنجا که 1 در زیر درخت راست کوچکتر از 2 است. بنابراین ، ما باید روش دیگری پیدا کنیم.

رویکرد کارآمد (رویکرد صحیح)

ما از دو متغیر حداقل و حداکثر برای تعریف دامنه زیر شاخه های چپ و راست خود استفاده خواهیم کرد. این به ما می گوید که آیا عناصر موجود در زیر شاخه سمت چپ در محدوده ای قرار دارند یا خیر. همانطور که ما درختان فرعی را تغییر می دهیم این محدوده همچنان تغییر خواهد کرد. این روش فقط برای از بین بردن نقصی است که با رویکرد ساده لوحانه ای روبرو هستیم. در آنجا ما نمی توانستیم تضمین کنیم که تمام عناصر موجود در زیر شاخه سمت چپ کوچکتر از ریشه خواهند بود. و همه عناصر موجود در زیر درخت راست از ریشه بیشتر خواهند بود. در ابتدا ، ما جستجوگر BST خود را با حداقل تنظیم شده به عنوان حداقل مقدار عدد صحیح و حداکثر به عنوان حداکثر مقدار عدد صحیح ، فراخوانی خواهیم کرد. زیرا این محدوده ای است که باید مقدار ریشه را تأمین کند. اکنون ما حداکثر برای زیر شاخه سمت چپ را به عنوان root-value-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

برنامه جاوا برای بررسی اینکه آیا یک درخت باینری 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 گره در درخت وجود دارد.