Екілік іздеу ағашы


Күрделілік дәрежесі оңай
Жиі кіреді Amazon DBOI Фуркиттер Infosys Microsoft
Екілік іздеу ағашы Екілік ағаш теория ағаш

Екілік іздеу ағашы - екілік ағаш деректерді сұрыпталған күйде сақтауға мүмкіндік беретін кейбір ережелермен.

Бұл қалай екілік ағаш демек, түйін максимум 2 баладан тұруы мүмкін.

Екілік іздеу ағашы түйінінің құрылымы

 

Екілік іздеу ағашы

Екілік ағаштың екілік іздеу ағашы болу ережелері

  1. Түйіннің сол жақ кіші ағашында орналасқан түйіндер сол түйіннен аз болуы керек.
  2. Түйіннің оң ішкі ағашында орналасқан түйіндер сол түйіннен үлкен болуы керек.
  3. Жоғарыда аталған екі шарт ағаштағы барлық түйіндерге қатысты болуы керек.

мысал

Екілік іздеу ағашы

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.

Әр түйін үшін BST шарттарын тексеруді әрқашан ұмытпаңыз.

Мысалға:

Бұл екілік іздеу ағашы емес.

Екілік іздеу ағашы

Екілік іздеу ағашының артықшылықтары

  1. Іздеуді O (log (h)) арқылы жүзеге асыруға болады, мұндағы h - BST биіктігі, өйткені біз мәліметтердің BST жүйесінде сұрыпталған түрде сақталатын қасиетін пайдаланып екілік іздеуді қолдана аламыз.
  2. Деректерді сұрыпталған түрде енгізу O (log (h)) түрінде де жүзеге асырылады, ал массивтер мен байланыстырылған тізім сияқты басқа деректер құрылымдары бұл операция O (n) уақытты алады.

Екілік іздеу ағашын құру

Алгоритм

  1. Енгізілетін мәні бар түйін жасаңыз
  2. insertBST (түйін, мән)
    1. Егер root == NULL болса, онда құрылған түйінді қайтарыңыз
    2. егер root-> мәні <кілт:
      • Құрылған түйінді оң жақ ағашқа салыңыз
      • root-> right = insertBST (root-> right, мән)
    3.  Егер root-> value> кілт болса:
      • Құрылған түйінді сол жақ ағашқа салыңыз
      • root-> left = insertBST (root-> сол жақ, мән)
  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-нің сол жағына орналастырылуы керек.

Екілік іздеу ағашын енгізу

C ++ бағдарламасы

#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);
}

JAVA бағдарламасы

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-> 

Құрылған ағаштың құрылымы

Әдебиеттер тізімі