ثنائی تلاش درخت


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون ڈی بی او آئی۔ فورکائٹس انفوسس مائیکروسافٹ
ثنائی تلاش درخت ثنائی درخت کی تھیوری اور درخت

ایک بائنری تلاش کا درخت بائنری ہے درخت کچھ اصولوں کی مدد سے جو ہمیں اعداد و شمار کو الگ الگ فیشن میں برقرار رکھنے کی اجازت دیتا ہے۔

جیسے یہ ہے a بائنری ٹری لہذا ، نوڈ میں زیادہ سے زیادہ 2 بچے پیدا ہوسکتے ہیں۔

بائنری سرچ ٹری نوڈ کی ساخت

 

ثنائی تلاش درخت

ثنائی درخت بائنری سرچ ٹری ہونے کے قواعد

  1. نوڈ کے بائیں سب ٹری میں موجود نوڈس اس نوڈ سے کم ہونا چاہئے۔
  2. نوڈ کے دائیں سب ٹری میں موجود نوڈس اس نوڈ سے زیادہ ہونا چاہئے۔
  3. درخت میں موجود تمام نوڈس کے ل The مذکورہ بالا دو شرائط درست ہونی چاہ.۔

مثال کے طور پر

ثنائی تلاش درخت

Left subtree of 8 contains: 5, 3, 7 which are smaller than 8

Right subtree of 8 contains: 16, 18 which are greater than 8

Left subtree of 5 contains: 3 which is smaller than 5

Right subtree of 5 contains: 7 which is greater than 5

Left subtree of 16 does not contain any node.

Right subtree of 16 contains: 18 which is greater than 16

3, 7, 18 are leaf nodes hence there will be no left and right subtree present.

ہمیشہ ہر نوڈ کے لئے بی ایس ٹی کے حالات معلوم کرنا یاد رکھیں۔

مثال کے طور پر:

یہ بائنری سرچ ٹری نہیں ہے۔

ثنائی تلاش درخت

ثنائی تلاش درخت کے فوائد

  1. او (لاگ (ایچ)) میں تلاش کی جاسکتی ہے جہاں ایچ بی ایس ٹی کی اونچائی ہے کیوں کہ ہم اس پراپرٹی کا استعمال کرتے ہوئے اس پر بائنری سرچ لگاسکتے ہیں کہ ڈیٹا کو ایک ترتیب انداز میں بی ایس ٹی میں اسٹور کیا جاتا ہے۔
  2. ترتیب شدہ فیشن میں اعداد و شمار کا اندراج O (لاگ (h)) میں بھی کیا جاتا ہے ، جبکہ دیگر اعداد و شمار کے ڈھانچے جیسے اری اور منسلک فہرست میں اس آپریشن کو O (n) کا وقت لگے گا۔

ثنائی تلاش درخت کی تشکیل

الگورتھم

  1. داخل ہونے والی قدر کے ساتھ نوڈ بنائیں
  2. insertBST (نوڈ ، قدر)
    1. اگر جڑ == NULL تو تخلیق شدہ نوڈ کو لوٹائیں
    2. اگر روٹ-> قدر <کلید:
      • دائیں سب ٹری میں تخلیق شدہ نوڈ داخل کریں
      • جڑ-> دائیں = insertBST (روٹ-> دائیں ، قدر)
    3.  اگر روٹ-> قدر> کلید:
      • تخلیق شدہ نوڈ کو بائیں سب ٹری میں داخل کریں
      • جڑ-> بائیں = داخل کریں بی ایس ٹی (روٹ-> بائیں ، قیمت)
  1. واپس جڑ

آئیے اسے ایک مثال کے ساتھ سمجھیں:

عدد کی صف پر غور کریں [4، 7، 2، 8، 5]

آئیے ترتیب میں ترتیب سے ہر عنصر کو لے کر بی ایس ٹی بنائیں

1 مرحلہ: 4 داخل کریں

جیسا کہ جڑ ناخن ہے ، لہذا نو تشکیل شدہ نوڈ کو جڑ کی طرح بنائیں۔

ثنائی تلاش درخت

2 مرحلہ: 7 داخل کریں

جڑ کی قیمت 4 ہے ، لہذا جڑ کے دائیں میں 7 ہونا چاہئے۔

ثنائی تلاش درخت

3 مرحلہ: 2 داخل کریں

جڑ کی قیمت 4 ہے ، لہذا جڑ کے بائیں میں 2 رکھنا چاہئے۔

4 مرحلہ: 8 داخل کریں

جڑ کی قیمت 4 ہے ، لہذا 8 کو جڑ کے دائیں میں رکھنا چاہئے۔

اب ہم 7 کی جانچ کریں گے ، جیسا کہ 7 <8 لہذا 8 کو 7 کے دائیں میں رکھنا چاہئے۔

5 مرحلہ: 5 داخل کریں

جڑ کی قیمت 4 ہے ، لہذا 5 کو جڑ کے دائیں میں رکھنا چاہئے۔

اب ہم 7 کی جانچ کریں گے ، جیسا کہ 7> 5 لہذا 5 کو 7 کے بائیں میں رکھنا چاہئے۔

ثنائی تلاش درخت کا نفاذ

سی ++ پروگرام

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

struct node
{
    int value;
    struct node* left;
    struct node* right;
    node(int value){             // constructor
        this->value = value;
        this->left = NULL;
        this->right = NULL;
    }
};
struct node* insertBST(node* root, int value)
{
    if (root == NULL) 
        return new node(value);                       // return newly created node

    if (value < root->value)                         // value should be inserted in the left subtree
        root->left  = insertBST(root->left, value);
    else if (value > root->value)                    // value should be inserted in the right subtree
        root->right = insertBST(root->right, value);   
    return root;
}

void inorder(node* root){
    if(root == NULL) 
        return;
    inorder(root->left);
    cout<<root->value<<"-> ";
    inorder(root->right);
}


int main(){
    node *root = NULL;
    root = insertBST(root, 10);     //make the first created node as root
    insertBST(root, 5);
    insertBST(root, 4);
    insertBST(root, 16);
    insertBST(root, 2);
    insertBST(root, 12);
    insertBST(root, 17);

    inorder(root);
}

جاوا پروگرام

class Node { 
    int value; 
    Node left, right; 
  
    public Node(int v) { //constructor
        value = v; 
        left = null;
        right = null; 
    } 
};
class Main { 
    public static Node insertBST(Node root, int value) { 
        if (root == null) { 
            return new Node(value);                            // return newly created node
        }
        if (value < root.value)                               // value should be inserted in the left subtree
            root.left = insertBST(root.left, value); 
        else if (value > root.value)                         // value should be inserted in the right subtree
            root.right = insertBST(root.right, value); 
        return root; 
    } 
    public static void inorder(Node root) { 
        if (root != null) { 
            inorder(root.left); 
            System.out.print(root.value+"-> "); 
            inorder(root.right); 
        } 
    } 
    public static void main(String[] args) { 
        Node root = null; 
        
        root = insertBST(root, 10); //make the first created node as root 
        insertBST(root, 5); 
        insertBST(root, 4); 
        insertBST(root, 16); 
        insertBST(root, 2); 
        insertBST(root, 12); 
        insertBST(root, 17); 
        
        inorder(root);
    } 
}
2-> 4-> 5-> 10-> 12-> 16-> 17-> 

پیدا درخت کی ساخت

حوالہ جات