Μενού

Δυαδική αναζήτηση Δέντρο C ++: Εφαρμογή BST και λειτουργίες με παραδείγματα

  • Κύριος
  • Αλλα
  • Δυαδική αναζήτηση Δέντρο C ++: Εφαρμογή BST και λειτουργίες με παραδείγματα

binary search tree c

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Λεπτομερές σεμινάριο για το Δυαδικό Δέντρο Αναζήτησης (BST) στο C ++ που περιλαμβάνει Λειτουργίες, Εφαρμογή C ++, Πλεονεκτήματα και Παραδείγματα Προγραμμάτων:

Ένα Δυαδικό Δέντρο Αναζήτησης ή BST όπως ονομάζεται ευρέως είναι ένα δυαδικό δέντρο που πληροί τις ακόλουθες προϋποθέσεις:

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

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

=> Δείτε την ολοκληρωμένη σειρά προπόνησης C ++ εδώ.

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

Τι θα μάθετε:

Δυαδική αναζήτηση Δέντρο C ++

Ένα δείγμα BST φαίνεται παρακάτω.

Δείγμα BST

Τα δέντρα δυαδικής αναζήτησης αναφέρονται επίσης ως 'Διαταγμένα δυαδικά δέντρα' λόγω αυτής της συγκεκριμένης σειράς των κόμβων.

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

Τώρα ας συζητήσουμε μερικές βασικές λειτουργίες του BST.

Βασικές λειτουργίες

# 1) Εισαγωγή

Η λειτουργία εισαγωγής προσθέτει έναν νέο κόμβο σε ένα δέντρο δυαδικής αναζήτησης.

Ο αλγόριθμος για τη λειτουργία εισαγωγής δέντρου δυαδικής αναζήτησης δίνεται παρακάτω.

εφαρμογή μετατροπέα youtube σε mp4 για Android
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Όπως φαίνεται στον παραπάνω αλγόριθμο, πρέπει να διασφαλίσουμε ότι ο κόμβος είναι τοποθετημένος στην κατάλληλη θέση, ώστε να μην παραβιάζουμε την παραγγελία BST.

Εισαγωγή λειτουργίας σε BST

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

# 2) Διαγραφή

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

Ως εκ τούτου, ανάλογα με τον κόμβο που πρέπει να διαγράψουμε, έχουμε τις ακόλουθες περιπτώσεις για διαγραφή στο BST:

# 1) Όταν ο κόμβος είναι ένας κόμβος φύλλων

Όταν ο κόμβος που πρόκειται να διαγραφεί είναι ένας κόμβος φύλλων, τότε διαγράφουμε άμεσα τον κόμβο.

Ο κόμβος είναι ένας κόμβος φύλλων

# 2) Όταν ο κόμβος έχει μόνο ένα παιδί

Όταν ο κόμβος που πρόκειται να διαγραφεί έχει μόνο ένα παιδί, τότε αντιγράφουμε το παιδί στον κόμβο και διαγράφουμε το παιδί.

Ο κόμβος έχει μόνο ένα παιδί

# 3) Όταν ο κόμβος έχει δύο παιδιά

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

Ο κόμβος έχει δύο παιδιά

Στο παραπάνω δέντρο για να διαγράψετε τον κόμβο 6 με δύο παιδιά, βρίσκουμε πρώτα τον διάδοχο διάδοχο για αυτόν τον κόμβο που πρέπει να διαγραφεί. Βρίσκουμε τον διάδοχο εντοπισμού βρίσκοντας την ελάχιστη τιμή στο σωστό υποδένδρο. Στην παραπάνω περίπτωση, η ελάχιστη τιμή είναι 7 στο σωστό υποδένδρο. Το αντιγράφουμε στον κόμβο για διαγραφή και στη συνέχεια διαγράφουμε τον διάδοχο παραγγελίας.

# 3) Αναζήτηση

Η λειτουργία αναζήτησης του BST αναζητά ένα συγκεκριμένο στοιχείο που αναγνωρίζεται ως «κλειδί» στο BST. Το πλεονέκτημα της αναζήτησης ενός αντικειμένου στο BST είναι ότι δεν χρειάζεται να αναζητήσουμε ολόκληρο το δέντρο. Αντί για την παραγγελία στο BST, συγκρίνουμε απλώς το κλειδί με τη ρίζα.

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

Ακολουθεί ο αλγόριθμος για μια λειτουργία αναζήτησης στο BST.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

Λειτουργία αναζήτησης σε BST

Αν θέλουμε να αναζητήσουμε ένα κλειδί με την τιμή 6 στο παραπάνω δέντρο, τότε πρώτα συγκρίνουμε το κλειδί με τον ριζικό κόμβο, δηλαδή εάν (6 == 7) => Όχι εάν (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Στη συνέχεια κατεβαίνουμε στο αριστερό υποδένδρο. Εάν (6 == 5) => Όχι.

Εάν (6 Όχι, αυτό σημαίνει 6> 5 και πρέπει να κινηθούμε προς τα δεξιά.

Εάν (6 == 6) => Ναι; το κλειδί βρέθηκε.

# 4) Διασχίσεις

Έχουμε ήδη συζητήσει τις διασταυρώσεις για το δυαδικό δέντρο. Στην περίπτωση του BST, μπορούμε επίσης να διασχίσουμε το δέντρο για να εισέλθουμε στο Order, preorder ή postOrder. Στην πραγματικότητα, όταν διασχίζουμε το BST στην ακολουθία Inorder01, τότε παίρνουμε την ταξινομημένη ακολουθία.

Το έχουμε δείξει στην παρακάτω εικόνα.

διασταυρώσεις

Οι διασταυρώσεις για το παραπάνω δέντρο είναι οι εξής:

Διαδρομή εσωτερικής γραμμής (lnr): 3 5 6 7 8 9 10
Προπαραγγελία διέλευσης (nlr): 7 5 3 6 9 8 10
Διαδρομή μετά την παραγγελία (lrn): 3 6 5 8 10 9 7

Απεικόνιση

Ας δημιουργήσουμε ένα Δυαδικό Δέντρο Αναζήτησης από τα δεδομένα που δίνονται παρακάτω.

45 30 60 65 70

Ας πάρουμε το πρώτο στοιχείο ως τον ριζικό κόμβο.

# 1) 45

ριζικός κόμβος

Στα επόμενα βήματα, θα τοποθετήσουμε τα δεδομένα σύμφωνα με τον ορισμό του δέντρου δυαδικής αναζήτησης, δηλαδή εάν τα δεδομένα είναι μικρότερα από τον γονικό κόμβο, τότε θα τοποθετηθούν στο αριστερό παιδί και εάν τα δεδομένα είναι μεγαλύτερα από τον γονικό κόμβο, τότε θα είναι το σωστό παιδί.

Αυτά τα βήματα φαίνονται παρακάτω.

# 2) 30

Δέντρο δυαδικής αναζήτησης Βήμα 1 30

# 3) 60

Δέντρο δυαδικής αναζήτησης Βήμα 2 60

# 4) 65

11 Δυαδικό βήμα αναζήτησης δέντρου3

# 5) 70

Δυαδικό δέντρο αναζήτησης βήμα 4

Όταν εκτελούμε το inorder traversal στο παραπάνω BST που μόλις κατασκευάσαμε, η ακολουθία έχει ως εξής.

Διαδοχική εγκάρσια ακολουθία

Μπορούμε να δούμε ότι η εγκάρσια ακολουθία έχει στοιχεία διατεταγμένα σε αύξουσα σειρά.

Binary Search Tree Implementation C ++

Ας δείξουμε το BST και τις λειτουργίες του χρησιμοποιώντας την εφαρμογή C ++.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Παραγωγή:

Δέντρο δυαδικής αναζήτησης δημιουργήθηκε (Inorder traversal):

30 40 60 65 70

Διαγραφή κόμβου 40

Inorder traversal για το τροποποιημένο Δυαδικό Δέντρο Αναζήτησης:

30 60 65 70

Στο παραπάνω πρόγραμμα, εξάγουμε το BST για διαδοχική σειρά.

Πλεονεκτήματα του BST

# 1) Η αναζήτηση είναι πολύ αποτελεσματική

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

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

τι είναι ένα mac 7z αρχείο

# 2) Αποτελεσματική εργασία σε σύγκριση με πίνακες και συνδεδεμένες λίστες

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

# 3) Εισαγωγή και διαγραφή είναι ταχύτερη

Οι λειτουργίες εισαγωγής και διαγραφής είναι επίσης γρηγορότερες σε σύγκριση με άλλες δομές δεδομένων, όπως συνδεδεμένες λίστες και πίνακες.

Εφαρμογές της BST

Μερικές από τις σημαντικότερες εφαρμογές του BST είναι οι εξής:

  • Το BST χρησιμοποιείται για την εφαρμογή ευρετηρίου πολλαπλών επιπέδων σε εφαρμογές βάσης δεδομένων.
  • Το BST χρησιμοποιείται επίσης για την υλοποίηση κατασκευών όπως ένα λεξικό.
  • Το BST μπορεί να χρησιμοποιηθεί για την εφαρμογή διαφόρων αποτελεσματικών αλγορίθμων αναζήτησης.
  • Το BST χρησιμοποιείται επίσης σε εφαρμογές που απαιτούν μια ταξινομημένη λίστα ως είσοδος όπως τα ηλεκτρονικά καταστήματα.
  • Τα BST χρησιμοποιούνται επίσης για την αξιολόγηση της έκφρασης χρησιμοποιώντας δέντρα έκφρασης.

συμπέρασμα

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

Το Inorder traversal του BST μας δίνει την ταξινομημένη ακολουθία αντικειμένων σε αύξουσα σειρά. Όταν τα BST χρησιμοποιούνται για αναζήτηση, είναι πολύ αποτελεσματικό και γίνεται εντός χρονικού διαστήματος. Τα BST χρησιμοποιούνται επίσης για μια ποικιλία εφαρμογών όπως η κωδικοποίηση του Huffman, η πολυεπίπεδη ευρετηρίαση σε βάσεις δεδομένων κ.λπ.

=> Διαβάστε εδώ τη δημοφιλή εκπαιδευτική σειρά C ++ εδώ.

Συνιστώμενη ανάγνωση

^