Ҷустуҷӯ ва дохилкунии дарахтони ҷустуҷӯи бинарӣ


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon DBOI Фараж GE Тандурустӣ MAQ Microsoft UHG Optum
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Теория Дарахт

Изҳороти мушкилот

Алгоритми нависед барои ҷустуҷӯ ва гузоштан дар дарахти ҷустуҷӯи бинарӣ. Пас, он чизе, ки мо карданӣ ҳастем, ин аст, ки баъзе элементҳоро аз вуруд ба дарахти ҷустуҷӯи бинарӣ дохил кунем. Ҳар вақте, ки ягон чизи муайянеро талаб кунад, мо онро дар байни унсурҳои BST ҷустуҷӯ хоҳем кард (кӯтоҳ барои дарахти ҷустуҷӯи бинарӣ).

мисол

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

 

Дарахти ҷустуҷӯи бинарӣ чист?

Дарахти ҷустуҷӯи бинарӣ як навъи махсуси дарахти дуӣ мебошад, ки дорои хосиятҳои зерин мебошад,

  1. Ҳама гиреҳҳо аз гиреҳи кунунӣ хурдтар дар зери дарахти чапи он мавҷуданд.
  2. Ҳама гиреҳҳо аз гиреҳи ҷорӣ бузургтар дар зердарахти рости он мавҷуданд.
  3. Зердарахти чап ва рости гиреҳ низ дарахти ҷустуҷӯи дуӣ мебошад ва унсурҳои такроршаванда вуҷуд надоранд.

Ҷустуҷӯ

Алгоритм

Дарахти ҷустуҷӯи бинарӣ маълумотро дар a нигоҳ медорад мураттаб карда шудааст роҳ (ҳамчун он убур бо тартиби ба маълумоти мураттаб оварда мерасонад). Ҳамин тавр, ҷустуҷӯ дар 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.

Мураккабии вақт = Эй (н)

Азбаски мо дар бадтарин ҳолат тамоми дарахтро тай карданием. Бадтарин ҳолат метавонад ин бошад, ки мо дарахти каҷ дошта бошем ва арзиши ҳадафи худро ҳамчун барги дарахт дошта бошем. Дар омади гап, ҳам ҷустуҷӯ ва ҳам дар дохили дарахти ҷустуҷӯи бинарӣ мураккабии якхела доранд.

Мураккабии фазо = О (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) мусоидат мекунад.

Мураккабии фазо = О (1)

Дар ин ҷо, азбаски мо ягон арзиши ба ҳар як гиреҳ мувофиқро нигоҳ надорем. Мо мураккабии доимии фазоро дорем.

 

рамз

Кодекси JAVA барои ҷустуҷӯ ва замима дар дарахти ҷустуҷӯи бинарӣ

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 ++ Кодекс барои ҷустуҷӯ ва дохилкунӣ дар Tree Binary Search

#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