Дрво за бинарно пребарување


Ниво на тешкотија Лесно
Често прашувано во Амазон ДБОИ Фуркити Infosys Мајкрософт
Дрво за бинарно пребарување Бинарно дрво Теорија Дрво

Дрво за бинарно пребарување е Бинарно дрво со некои правила што ни овозможуваат да ги одржуваме податоците на подреден начин.

Како што е бинарно дрво па затоа, јазол може да има најмногу 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, value)
    3.  Ако root-> вредност> клуч:
      • Вметнете го креираниот јазол во левото подстево
      • root-> лево = insertBST (root-> лево, вредност)
  1. Врати го коренот

Ајде да го разбереме со пример:

Размислете за низа цел број [4, 7, 2, 8, 5]

Ајде да создадеме BST со земање на секој елемент од низата последователно

Чекор 1: Вметнете 4

Бидејќи коренот е нула, направете го новосоздадениот јазол како root.

Дрво за бинарно пребарување

Чекор 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);
}

Програма ЈАВА

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

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

Референци