Δυαδική Αναζήτηση Δέντρων Αναζήτηση και Εισαγωγή


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα DBOI Φανατικοί GE Healthcare MAQ Microsoft UHG Optum
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Θεωρία Δέντρο

Δήλωση προβλήματος

Γράψτε έναν αλγόριθμο για εκτέλεση αναζήτησης και εισαγωγή στο Δυαδικό Δέντρο Αναζήτησης. Έτσι, αυτό που πρόκειται να κάνουμε είναι να εισαγάγουμε μερικά από τα στοιχεία από την εισαγωγή σε ένα δέντρο δυαδικής αναζήτησης. Κάθε φορά που σας ζητείται να αναζητήσετε ένα συγκεκριμένο στοιχείο, θα το αναζητάμε μεταξύ των στοιχείων στο BST (συντομογραφία για το Δυαδικό Δέντρο αναζήτησης).

Παράδειγμα

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

 

Τι είναι το Δυαδικό Δέντρο Αναζήτησης;

Το Δυαδικό Δέντρο Αναζήτησης είναι ένα ειδικό είδος Δυαδικού Δέντρου που ακολουθεί τις ακόλουθες ιδιότητες,

  1. Όλοι οι κόμβοι μικρότεροι από τον τρέχοντα κόμβο υπάρχουν στο αριστερό υποδένδρο του.
  2. Όλοι οι κόμβοι μεγαλύτεροι από τον τρέχοντα κόμβο υπάρχουν στο σωστό υποδένδρο του.
  3. Το αριστερό και το δεξιό δευτερεύον δέντρο ενός κόμβου είναι επίσης το Δυαδικό Δέντρο αναζήτησης και δεν υπάρχουν επαναλαμβανόμενα στοιχεία.

Αναζήτηση

Αλγόριθμος

Το Δυαδικό Δέντρο αναζήτησης αποθηκεύει τα δεδομένα σε ένα ταξινομημένο τρόπος (όπως είναι εγκάρσια διαδοχή οδηγεί σε ταξινομημένα δεδομένα). Έτσι, η αναζήτηση στο BST είναι αρκετά απλή και εύκολη.

Ελέγχουμε εάν η ρίζα ισούται με τον κόμβο στόχου, εάν ναι, επιστρέψτε αληθής, αλλιώς εάν ο στόχος είναι μικρότερος από την τιμή της ρίζας, το ψάχνουμε στο αριστερό υποδένδρο αλλιώς το ψάχνουμε στο δεξιό υποδένδρο.

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.

Πολυπλοκότητα χρόνου = O (n)

Δεδομένου ότι πρόκειται να διασχίσουμε ολόκληρο το δέντρο στη χειρότερη περίπτωση. Η χειρότερη περίπτωση μπορεί να είναι ότι έχουμε ένα λοξό δέντρο και έχουμε την τιμή-στόχο μας ως το φύλλο του δέντρου. Παρεμπιπτόντως, τόσο η αναζήτηση όσο και η εισαγωγή στο Δυαδικό Δέντρο αναζήτησης έχουν την ίδια χρονική πολυπλοκότητα.

Διαστημική πολυπλοκότητα = Ο (1)

Δεδομένου ότι δεν χρησιμοποιούμε έναν πίνακα ή δεν αποθηκεύουμε τιμές για κόμβους κατά τη διάρκεια του αλγορίθμου. Έτσι, η αναζήτηση γίνεται στην πολυπλοκότητα του διαστήματος O (1). Το ίδιο ισχύει και για την πολυπλοκότητα του χώρου, τόσο η αναζήτηση όσο και η εισαγωγή στο Δυαδικό Δέντρο αναζήτησης είναι αλγόριθμοι διαστημικότητας O (1).

Εισαγωγή

Η εισαγωγή νέου κόμβου στο BST είναι παρόμοια με την αναζήτηση. Ψάχνουμε για την πρώτη κενή θέση στο BST, ικανοποιώντας τις ιδιότητες του BST και εισάγουμε τον νέο Κόμβο σε αυτό το μέρος.

Δυαδική Αναζήτηση Δέντρων Αναζήτηση και Εισαγωγή

Αλγόριθμος

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.

Χρόνος πολυπλοκότητας = O (n)

Εδώ πάλι, έχουμε μια υπόθεση ότι παρέχουμε στοιχεία είτε σε αύξουσα είτε σε φθίνουσα σειρά, ή έτσι ώστε να καταλήξουμε να έχουμε ένα λοξό δέντρο. Στη συνέχεια, σε αυτήν την περίπτωση, εάν το στοιχείο που πρόκειται να εισαχθεί είναι τέτοιο που θα γίνει φύλλο. Θα πρέπει να διασχίσουμε ολόκληρο το δέντρο. Συμβάλλοντας έτσι στην πολυπλοκότητα του O (n) χρόνου.

Διαστημική πολυπλοκότητα = Ο (1)

Εδώ, αφού δεν αποθηκεύσαμε καμία τιμή που να αντιστοιχεί σε κάθε κόμβο. Έχουμε συνεχή πολυπλοκότητα στο χώρο.

 

Κώδικας

Κωδικός JAVA για αναζήτηση και εισαγωγή στο Δυαδικό Δέντρο Αναζήτησης

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

Κωδικός C ++ για αναζήτηση και εισαγωγή στο Δυαδικό Δέντρο Αναζήτησης

#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