İkili Axtarış Ağacı

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon DBOI Fourkites Infosys microsoft
İkili Axtarış Ağacı İkili ağac nəzəriyyə AğacBaxılıb 41

İkili axtarış ağacı İkilidir ağac məlumatları sıralanmış şəkildə saxlamağımızı təmin edən bəzi qaydalarla.

Olduğu kimi ikili ağac bu səbəbdən bir düyün maksimum 2 uşağa sahib ola bilər.

İkili Axtarış Ağacı qovşağının quruluşu

 

İkili Axtarış AğacıPin

İkili ağacın İkili axtarış ağacı olması qaydaları

  1. Bir düyünün sol alt ağacında mövcud olan qovşaqlar bu düyündən az olmalıdır.
  2. Bir düyünün sağ alt ağacında olan qovşaqlar həmin düyündən daha böyük olmalıdır.
  3. Yuxarıda göstərilən iki şərt ağacdakı bütün qovşaqlar üçün doğru olmalıdır.

misal

İkili Axtarış AğacıPin

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.

Həmişə hər bir qovşaq üçün BST şərtlərini yoxlamağı unutmayın.

Misal üçün:

Bu İkili Axtarış Ağacı deyil.

İkili Axtarış AğacıPin

İkili Axtarış Ağacının üstünlükləri

  1. Axtarış O (log (h)) -də edilə bilər, burada h BST hündürlüyüdür, çünki məlumatların BST-də sıralanmış qaydada saxlanıldığı xüsusiyyətdən istifadə edərək ikili axtarış tətbiq edə bilərik.
  2. Verilənlərin sıralanmış qaydada daxil edilməsi O (log (h)) da həyata keçirilir, halbuki massivlər və əlaqəli siyahı kimi digər məlumat strukturları bu əməliyyat O (n) vaxt aparacaqdır.

İkili axtarış ağacının yaradılması

Alqoritm

  1. Daxil ediləcək dəyəri olan bir qovşaq yaradın
  2. insertBST (düyün, dəyər)
    1. Root == NULL olarsa, yaradılan düyünü qaytarın
    2. əgər kök-> dəyər <düymə:
      • Yaradılan qovluğu sağ alt ağacda yerləşdirin
      • root-> right = insertBST (kök-> sağ, dəyər)
    3.  Kök-> dəyər> açar varsa:
      • Yaradılan qovşağı sol alt ağacda yerləşdirin
      • kök-> sol = insertBST (kök-> sol, dəyər)
  1. Kökə qayıdın

Bir nümunə ilə başa düşək:

Bir tam ədədi nəzərdən keçirək [4, 7, 2, 8, 5]

Hər elementi ardıcıl olaraq serialdan götürərək bir BST yarataq

1 Adım: 4 əlavə edin

Kök boş olduğu üçün yeni yaradılan düyünü kök olaraq düzəldin.

İkili Axtarış Ağacı

2 Adım: 7 əlavə edin

Kök dəyəri 4-dür, bu səbəbdən kök 7-də olmalıdır.

İkili Axtarış AğacıPin

3 Adım: 2 əlavə edin

Kök dəyəri 4-dür, bu səbəbdən 2 kökdən sola yerləşdirilməlidir.

Pin

4 Adım: 8 əlavə edin

Kök dəyəri 4-dür, buna görə 8 kök sağına yerləşdirilməlidir.

İndi 7 ilə yoxlayacağıq, çünki 7 <8, buna görə 8 7-nin sağında yerləşdirilməlidir.

Pin

5 Adım: 5 əlavə edin

Kök dəyəri 4-dür, buna görə 5 kök sağına yerləşdirilməlidir.

İndi 7 ilə yoxlayacağıq, çünki 7> 5 olduğundan 5-nin soluna 7 qoyulmalıdır.

Pin

İkili Axtarış Ağacının tətbiqi

C ++ Proqramı

#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 Proqramı

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

Yaradılan ağacın quruluşu

Pin

References

Translate »