برنامج للتحقق مما إذا كانت الشجرة الثنائية هي BST أم لا


مستوى الصعوبة سهل
كثيرا ما يطلب في Accolite أدوبي أمازون تجارة بوميرانج مجموعة الحقائق رمادي ميك ماي تريب Microsoft أوراكل غرف OYO كوالكوم Snapdeal في إم وير مختبرات وول مارت ووكر
شجرة البحث الثنائية شجرة ثنائية شجرة

المشكلة بيان

ينص "برنامج للتحقق مما إذا كانت الشجرة الثنائية BST أم لا" على أنه تم إعطاؤك شجرة ثنائية وتحتاج إلى التحقق مما إذا كانت الشجرة الثنائية تفي بخصائص شجرة البحث الثنائية. لذلك ، فإن الشجرة الثنائية لها الخصائص التالية: 

  1. يجب أن تحتوي الشجرة الفرعية اليسرى على عقد ذات قيمة أقل من الجذر
  2. يجب أن تحتوي الشجرة الفرعية الصحيحة على العقد التي تحتوي على بيانات أكبر من الجذر
  3. يجب أن تكون الشجرة الفرعية اليمنى واليسرى عبارة عن شجرة بحث ثنائية مما يعني أنه يجب عليهم اتباع خصائص شجرة البحث الثنائية.

مثال

إدخال

برنامج للتحقق مما إذا كانت الشجرة الثنائية هي BST أم لا

YES

Explanation: الشجرة المحددة تتبع كل خصائص شجرة البحث الثنائية. جميع العقد الموجودة في الشجرة الفرعية اليسرى أصغر من قيمة الجذر. وينطبق الشيء نفسه على الشجرة الفرعية اليمنى ، فالعقد لها قيمة أكبر من الجذر. والشجرة الفرعية اليسرى والشجرة الفرعية اليمنى تتبعان خصائص BST.

إدخال

NO

شرح: الشجرة لا تتبع خاصية BST، حيث يجب أن يكون لجميع العقد في الشجرة الفرعية اليسرى قيمة أصغر من الجذر.

نهج لبرنامج للتحقق مما إذا كانت الشجرة الثنائية BST أم لا

نهج ساذج (نهج خاطئ)

هنا نكتب ببساطة برنامجًا يتحقق مما إذا كان جذر الشجرة الفرعية اليسرى له قيمة أصغر من قيمة الجذر. وجذر الشجرة اليمنى أكبر من الجذر. ثم تحقق بشكل متكرر من الأشجار الفرعية اليمنى واليسرى. لكن هذا النهج خاطئ لأنه على الرغم من أن جذر الشجرة الفرعية الأيسر أصغر من الجذر. قد يكون هناك بعض العقد في الشجرة الفرعية اليسرى والتي لها قيمة أكبر مقارنة بالجذر. وبالمثل بالنسبة للشجرة الفرعية الصحيحة. لذلك ، في هذه الحالة ، فشل هذا النهج.

قم بتشغيل الخوارزمية على الشجرة المحددة (الصورة). سوف تجد على الرغم من أن الخوارزمية ستعيد أن الشجرة الثنائية المعطاة هي BST. ولكن بما أن 1 في الشجرة الفرعية اليمنى أصغر من 2. لذا ، فنحن بحاجة إلى إيجاد طريقة أخرى.

نهج فعال (النهج الصحيح)

سنستخدم متغيرين كحد أدنى وأقصى لتحديد نطاق الشجرة الفرعية اليمنى واليسرى. سيخبرنا هذا ما إذا كانت العناصر الموجودة في الشجرة الفرعية اليسرى تقع في نطاق ما. سيستمر هذا النطاق في التغيير مع استمرارنا في تغيير الأشجار الفرعية. تستخدم هذه الطريقة فقط لإزالة الخلل الذي نواجهه بأسلوب ساذج. لم نتمكن هناك من ضمان أن جميع العناصر في الشجرة الفرعية اليسرى ستكون أصغر من الجذر. وستكون جميع العناصر الموجودة في الشجرة الفرعية اليمنى أكبر من الجذر. في البداية ، سنقوم باستدعاء مدقق 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

تحليل التعقيد

تعقيد الوقت

على)، لأننا اجتازنا الشجرة فقط. ويكلف الاجتياز الفردي تعقيدًا زمنيًا خطيًا.

تعقيد الفضاء

يا (1) مساحة ثابتة لأننا استخدمنا فقط عددًا ثابتًا من المتغيرات ولكن البرنامج ككل يأخذ O (N) نظرًا لوجود العقد N في الشجرة.