بحث ثنائي شجرة البحث والإدراج


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون DBOI المتعصبون جنرال إلكتريك للرعاية الصحية MAQ Microsoft UHG Optum
شجرة البحث الثنائية شجرة ثنائية نظرية شجرة

المشكلة بيان

اكتب خوارزمية لإجراء البحث والإدراج في شجرة البحث الثنائية. إذن ما سنفعله هو إدخال بعض العناصر من الإدخال في شجرة بحث ثنائية. عندما يُطلب منك البحث عن عنصر معين ، سنبحث عنه بين العناصر في BST (اختصار لـ Binary Search Tree).

مثال

Insert 10
Insert 15
Search 5
Insert 5
Insert 18
Search 5
Insert 12
Search 10
false
true
true

 

ما هي شجرة البحث الثنائية؟

شجرة البحث الثنائية هي نوع خاص من الشجرة الثنائية التي تتبع الخصائص التالية ،

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

البحث

خوارزمية

Binary Search Tree يخزن البيانات في ملف فرز طريقة (كما لها اجتياز الطلب يؤدي إلى فرز البيانات). لذا ، فإن البحث في BST بسيط للغاية وسهل.

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

1. Check if root equals to the target node, if yes, return true, else go to step 2.
2. If the target is smaller than the root's value, search the target in the left sub-tree.
3. Else search the target in the right sub-tree.

تعقيد الوقت = O (ن)

بما أننا سنجتاز الشجرة بأكملها في أسوأ الحالات. أسوأ الحالات يمكن أن يكون لدينا شجرة منحرفة ولدينا القيمة المستهدفة لدينا مثل ورقة الشجرة. بالمناسبة ، كل من البحث والإدراج في Binary Search Tree لهما نفس التعقيد الزمني.

تعقيد الفضاء = يا (1)

نظرًا لأننا لا نستخدم مصفوفة أو نخزن قيمًا للعقد أثناء الخوارزمية. وبالتالي ، يحدث البحث في O (1) الفضاء التعقيد. الأمر نفسه ينطبق على تعقيد المساحة ، فكل من البحث والإدراج في شجرة البحث الثنائية هما خوارزميات تعقيد مساحة O (1).

إدخال

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

بحث ثنائي شجرة البحث والإدراج

خوارزمية

1. Allocate space for new Node, let it be node.
2. If root is null, make root as node and return.
3. If the value of new node is smaller than the root's value, insert the new node in the left sub-tree.
4. Else insert the new node in the right sub-tree.

تعقيد الوقت = O (ن)

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

تعقيد الفضاء = يا (1)

هنا لأننا لم نخزن أي قيمة مطابقة لكل عقدة. لدينا تعقيد فضاء ثابت.

 

رمز

كود جافا للبحث والإدراج في شجرة البحث الثنائية

class BSTSearchAndInsert {
    // class to represent node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static Node insertToBST(Node root, Node node) {
        // if root is null, then make root as node and return
        if (root == null) {
            root = node;
            return root;
        }

        // if node's value is less than root, insert it to left subtree
        if (node.data < root.data) {
            root.left = insertToBST(root.left, node);
        }
        // else insert it to right subtree
        else {
            root.right = insertToBST(root.right, node);
        }

        // return the updated root
        return root;
    }

    private static Node insert(Node root, int value) {
        // allocate memory for new node
        Node node = new Node(value);

        // insert the new node to tree
        return insertToBST(root, node);
    }

    private static boolean search(Node root, int val) {
        // if root is null, return false
        if (root == null) {
            return false;
        }

        // if root is equals to target, return true
        if (root.data == val) {
            return true;
        }
        // else if val is less than root, search in left subtree
        else if (val < root.data) {
            return search(root.left, val);
        }
        // else search in right subtree
        else {
            return search(root.right, val);
        }
    }

    public static void main(String[] args) {
        // Example
        Node root = null;
        root = insert(root, 10);
        root = insert(root, 15);
        System.out.println(search(root, 5));
        root = insert(root, 5);
        root = insert(root, 18);
        System.out.println(search(root, 5));
        root = insert(root, 12);
        System.out.println(search(root, 10));
    }
}
false
true
true

كود C ++ للبحث والإدراج في شجرة البحث الثنائية

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

Node* insertToBST(Node *root, Node *node) {
    // if root is null, then make root as node and return
    if (root == NULL) {
        root = node;
        return root;
    }
    
    // if node's value is less than root, insert it to left subtree
    if (node->data < root->data) {
        root->left = insertToBST(root->left, node);
    }
    // else insert it to right subtree
    else {
        root->right = insertToBST(root->right, node);
    }
    
    // return the updated root
    return root;
}

Node* insert(Node *root, int value) {
    // allocate memory for new node
    Node *node = new Node(value);
    
    // insert the new node to tree
    return insertToBST(root, node);
}

bool search(Node *root, int value) {
    // if root is null, return false
    if (root == NULL) {
        return false;
    }
    
    // if root is equals to target, return true
    if (root->data == value) {
        return true;
    }
    // else if val is less than root, search in left subtree
    else if (value < root->data) {
        return search(root->left, value);
    }
    // else search in right subtree
    else {
        return search(root->right, value);
    }
}

int main() {
    // Example
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 15);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 5);
    root = insert(root, 18);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 12);
    if (search(root, 10)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true
true