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


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад 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.

Ҳамеша фаромӯш накунед, ки шароити ҳар як гиреҳро тафтиш кунед.

Барои намуна:

Ин дарахти ҷустуҷӯи дуӣ нест.

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

Афзалиятҳои дарахти ҷустуҷӯи бинарӣ

  1. Ҷустуҷӯро дар O (log (h)) анҷом додан мумкин аст, ки h баландии BST аст, зеро мо метавонем бо истифода аз хосиятҳое, ки маълумот ба тариқи мураттаб дар BST ҳифз карда мешавад, ҷустуҷӯи бинариро дар он татбиқ кунем.
  2. Ворид кардани маълумот бо тартиби муқарраршуда инчунин бо O (log (h)) анҷом дода мешавад, дар ҳоле ки дигар сохторҳои додаҳо ба монанди массивҳо ва рӯйхати алоқаманд ин амал O (n) вақтро талаб мекунанд.

Эҷоди дарахти ҷустуҷӯи дуӣ

Алгоритм

  1. Бо арзиши гузошташуда гиреҳ эҷод кунед
  2. insertBST (гиреҳ, арзиш)
    1. Агар root == NULL, пас гиреҳи эҷодшударо баргардонед
    2. агар root-> value <key:
      • Гиреҳи эҷодшударо ба зери дарахти рост гузоред
      • root-> right = insertBST (root-> right, арзиш)
    3.  Агар root-> value> key:
      • Гиреҳи эҷодшударо ба дарахти чап гузоред
      • root-> left = insertBST (root-> left, арзиш)
  1. Решаро баргардонед

Биёед инро бо мисол фаҳмем:

Массиви бутунро баррасӣ кунед [4, 7, 2, 8, 5]

Ҳар як элементро аз массив пай дар пай гирифта, BST созем

Қадами 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-> 

Сохтори дарахти офаридашуда

Адабиёт