Хоёртын хайлтын мод


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны 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-> утга> түлхүүр бол:
      • Үүсгэсэн зангилааг зүүн дэд модонд оруулна уу
      • root-> left = insertBST (root-> зүүн, утга)
  1. Буцах үндэс

Үүнийг жишээн дээр ойлгоё.

Бүхэл тоон массивыг авч үзье [4, 7, 2, 8, 5]

Элемент бүрийг массиваас дараалан авч BST үүсгэе

1 Алхам: 4-ийг оруулна уу

Үндэс нь хоосон тул шинээр үүсгэсэн зангилааг root болгоно.

Хоёртын хайлтын мод

2 Алхам: 7-ийг оруулна уу

Root value нь 4 тул 7 нь root-ийн баруун талд байх ёстой.

Хоёртын хайлтын мод

3 Алхам: 2-ийг оруулна уу

Root value нь 4 тул root-ийн зүүн талд 2 байрлуулна.

4 Алхам: 8-ийг оруулна уу

Root value нь 4 тул root-ийн баруун талд 8 байрлуулах ёстой.

7 <7 тул 8-ыг 8-ийн баруун талд байрлуулах ёстой тул одоо бид 7-той харьцуулна.

5 Алхам: 5-ийг оруулна уу

Root value нь 4 тул root-ийн баруун талд 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-> 

Үүсгэсэн модны бүтэц

Ашигласан материал