Двоично дърво за търсене


Ниво на трудност Лесно
Често задавани в Амазонка DBOI Fourkites Infosys Microsoft
Двоично дърво за търсене Двоично дърво Теория Дърво

Двоично дърво за търсене е двоично дърво с някои правила, които ни позволяват да поддържаме данните по сортиран начин.

Тъй като е a двоично дърво следователно възел може да има максимум 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-> вдясно = insertBST (root-> вдясно, стойност)
    3.  Ако root-> стойност> ключ:
      • Поставете създадения възел в лявото поддърво
      • корен-> ляво = вмъкванеBST (корен-> ляво, стойност)
  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-> 

Структура на създаденото дърво

Препратки