Бинарно претраживање дрвета претраживања и уметања


Ниво тешкоће Лако
Често питани у амазонка ДБОИ Фанатици ГЕ Хеалтхцаре МАК мицрософт УХГ Оптум
Бинарно стабло претраживања Бинарно дрво теорија Дрво

Изјава о проблему

Напишите алгоритам за извршавање претраживања и уметања у бинарно стабло претраживања. Дакле, оно што ћемо урадити је да уметнемо неке елементе из уноса у бинарно стабло претраживања. Кад год буде затражено да претражимо одређени елемент, тражићемо га међу елементима у БСТ (скраћеница од Бинарно стабло претраживања).

Пример

Insert 10
Insert 15
Search 5
Insert 5
Insert 18
Search 5
Insert 12
Search 10
false
true
true

 

Шта је бинарно стабло претраживања?

Бинарно стабло претраживања је посебна врста бинарног стабла које следи следећа својства,

  1. Сви чворови мањи од тренутног чвора присутни су у његовом левом потстаблу.
  2. Сви чворови већи од тренутног чвора присутни су у његовом десном подстаблу.
  3. Лијево и десно подстабло чвора је такође Бинарно стабло претраживања и нема поновљених елемената.

Претраживање

Алгоритам

Бинарно дрво претраживања чува податке у а сортирано начин (као свој прелазак по реду води до сортираних података). Дакле, претраживање у БСТ-у је прилично једноставно и лако.

Проверавамо да ли је корен једнак циљном чвору, ако је одговор да, врати труе, у супротном ако је циљ мањи од вредности корена, претражујемо га у левом подстаблу, иначе га претражујемо у десном подстаблу.

1. Check if root equals to the target node, if yes, return true, else go to step 2.
2. If the target is smaller than the root's value, search the target in the left sub-tree.
3. Else search the target in the right sub-tree.

Сложеност времена = Он)

Пошто ћемо у најгорем случају прећи цело дрво. Најгори случај може бити да имамо искривљено дрво и имамо циљну вредност као лист дрвета. Иначе, и претраживање и уметање у бинарно стабло претраживања имају исту временску сложеност.

Сложеност простора = О (1)

С обзиром да током алгоритма не користимо низ или чувамо вредности за чворове. Дакле, претрага се јавља у сложености простора О (1). Исто важи и за сложеност простора, и претраживање и уметање у бинарно стабло претраживања су О (1) алгоритми сложености простора.

Инсертион

Уметање новог чвора у БСТ је слично претраживању. Тражимо прву празну позицију у БСТ, испуњавајући својства БСТ и убацујемо нови чвор на то место.

Бинарно претраживање дрвета претраживања и уметања

Алгоритам

1. Allocate space for new Node, let it be node.
2. If root is null, make root as node and return.
3. If the value of new node is smaller than the root's value, insert the new node in the left sub-tree.
4. Else insert the new node in the right sub-tree.

Сложеност времена = Он)

И овде имамо случај да нам се пружају елементи у редоследу повећавања или смањивања или такви да бисмо на крају могли имати искривљено дрво. У том случају, ако је елемент који се убацује такав да ће постати лист. Мораћемо да пређемо цело дрво. На тај начин доприносећи сложености времена О (н).

Сложеност простора = О (1)

Ево јер нисмо сачували ниједну вредност која одговара сваком чвору. Имамо сталну сложеност простора.

 

код

ЈАВА код за претраживање и уметање у бинарно стабло претраживања

class BSTSearchAndInsert {
    // class to represent node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static Node insertToBST(Node root, Node node) {
        // if root is null, then make root as node and return
        if (root == null) {
            root = node;
            return root;
        }

        // if node's value is less than root, insert it to left subtree
        if (node.data < root.data) {
            root.left = insertToBST(root.left, node);
        }
        // else insert it to right subtree
        else {
            root.right = insertToBST(root.right, node);
        }

        // return the updated root
        return root;
    }

    private static Node insert(Node root, int value) {
        // allocate memory for new node
        Node node = new Node(value);

        // insert the new node to tree
        return insertToBST(root, node);
    }

    private static boolean search(Node root, int val) {
        // if root is null, return false
        if (root == null) {
            return false;
        }

        // if root is equals to target, return true
        if (root.data == val) {
            return true;
        }
        // else if val is less than root, search in left subtree
        else if (val < root.data) {
            return search(root.left, val);
        }
        // else search in right subtree
        else {
            return search(root.right, val);
        }
    }

    public static void main(String[] args) {
        // Example
        Node root = null;
        root = insert(root, 10);
        root = insert(root, 15);
        System.out.println(search(root, 5));
        root = insert(root, 5);
        root = insert(root, 18);
        System.out.println(search(root, 5));
        root = insert(root, 12);
        System.out.println(search(root, 10));
    }
}
false
true
true

Ц ++ код за претраживање и уметање у бинарно стабло претраживања

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

Node* insertToBST(Node *root, Node *node) {
    // if root is null, then make root as node and return
    if (root == NULL) {
        root = node;
        return root;
    }
    
    // if node's value is less than root, insert it to left subtree
    if (node->data < root->data) {
        root->left = insertToBST(root->left, node);
    }
    // else insert it to right subtree
    else {
        root->right = insertToBST(root->right, node);
    }
    
    // return the updated root
    return root;
}

Node* insert(Node *root, int value) {
    // allocate memory for new node
    Node *node = new Node(value);
    
    // insert the new node to tree
    return insertToBST(root, node);
}

bool search(Node *root, int value) {
    // if root is null, return false
    if (root == NULL) {
        return false;
    }
    
    // if root is equals to target, return true
    if (root->data == value) {
        return true;
    }
    // else if val is less than root, search in left subtree
    else if (value < root->data) {
        return search(root->left, value);
    }
    // else search in right subtree
    else {
        return search(root->right, value);
    }
}

int main() {
    // Example
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 15);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 5);
    root = insert(root, 18);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 12);
    if (search(root, 10)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true
true