Δυαδικό δέντρο αναζήτησης (BST) με Παράδειγμα

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

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

Χαρακτηριστικά του Δυαδικού Δέντρου Αναζήτησης

Ένα BST αποτελείται από πολλαπλούς κόμβους και αποτελείται από τα ακόλουθα χαρακτηριστικά:

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

1. Υπάρχει ο κύριος κόμβος ή γονικός κόμβος επιπέδου 11. Κάτω από αυτόν, υπάρχουν αριστεροί και δεξιοί κόμβοι/κλάδοι με τις δικές τους τιμές κλειδιού.
2. Το δεξί υποδέντρο έχει τιμές κλειδιού μεγαλύτερες από τον γονικό κόμβο.
3. Το αριστερό υποδέντρο έχει τιμές κλειδιών μικρότερες από τον γονικό κόμβο.

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

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

Τύποι δυαδικών δέντρων

Τρία είδη δυαδικών δέντρων είναι:

• Πλήρες δυαδικό δέντρο: Όλα τα επίπεδα στο δέντρο είναι γεμάτα, με πιθανή εξαίρεση στο τελευταίο επίπεδο. Ομοίως, όλοι οι κόμβοι είναι γεμάτοι, με κατεύθυνση προς τα αριστερά.
• Πλήρες δυαδικό δέντρο: Όλοι οι κόμβοι έχουν 2 θυγατρικούς κόμβους εκτός από το φύλλο.
• Ισορροπημένο ή Τέλειο Δυαδικό Δέντρο: Στο δέντρο, όλοι οι κόμβοι έχουν δύο θυγατρικά στοιχεία. Επιπλέον, υπάρχει το ίδιο επίπεδο για κάθε υποκόμβο.

Μάθετε περισσότερα σχετικά με το Δυαδικό δέντρο στη δομή δεδομένων αν ενδιαφέρεσαι.

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

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

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

Η BST προσφέρει κυρίως τους ακόλουθους τρεις τύπους λειτουργιών για τη χρήση σας:

• Έρευνα: αναζητά το στοιχείο από το δυαδικό δέντρο.
• Εισάγετε: προσθέτει ένα στοιχείο στο δυαδικό δέντρο.
• Διαγράφω: διαγράφει το στοιχείο από ένα δυαδικό δέντρο.

Κάθε πράξη έχει τη δική της δομή και μέθοδο εκτέλεσης/ανάλυσης, αλλά η πιο περίπλοκη από όλες είναι η λειτουργία Διαγραφή.

Αναζήτηση Operaσμού

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

1. Το στοιχείο που θα αναζητηθεί είναι το 10.
2. Συγκρίνετε το στοιχείο με τον κόμβο ρίζας 12, 10 < 12, επομένως μετακινείστε στο αριστερό υποδέντρο. Δεν χρειάζεται να αναλύσετε το δεξί υποδέντρο.
3. Τώρα συγκρίνετε τον κόμβο 10 με τον κόμβο 7, 10 > 7, οπότε μετακινηθείτε στο δεξί υποδέντρο.
4. Στη συνέχεια, συγκρίνετε το 10 με τον επόμενο κόμβο, ο οποίος είναι 9, 10 > 9, κοιτάξτε στο δεξί υποδέντρο-θυγατρικό στοιχείο.
5. 10 αντιστοιχούν με την τιμή στον κόμβο, 10 = 10, επιστρέφουν την τιμή στον χρήστη.

Παρατσούκλι Code για αναζήτηση σε BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

Κύριο θέμα Operaσμού

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

1. Υπάρχει μια λίστα με 6 στοιχεία που πρέπει να εισαχθούν σε ένα BST με τη σειρά από αριστερά προς τα δεξιά.
2. Εισαγάγετε το 12 ως ριζικό κόμβο και συγκρίνετε τις επόμενες τιμές 7 και 9 για να τις εισαγάγετε ανάλογα στο δεξί και αριστερό υποδέντρο.
3. Συγκρίνετε τις υπόλοιπες τιμές 19, 5 και 10 με τον κόμβο ρίζας 12 και τοποθετήστε τις ανάλογα. 19 > 12, τοποθετήστε τον ως το δεξί παιδί του 12. 5 < 12 και 5 < 7, επομένως τοποθετήστε τον ως το αριστερό παιδί του 7. Τώρα συγκρίνετε 10, 10 είναι < 12 και 10 είναι > 7 και 10 είναι > 9, τοποθετήστε το 10 ως το δεξί υποδέντρο του 9.

Ψευδοκώδικας για την εισαγωγή ενός κόμβου στο BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Διαγραφή Operaσεις

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

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

• Περίπτωση 1 – Κόμβος με μηδενικά παιδιά: Αυτή είναι η ευκολότερη περίπτωση, απλώς πρέπει να διαγράψετε τον κόμβο που δεν έχει άλλα παιδιά στα δεξιά ή στα αριστερά.
• Περίπτωση 2 – Κόμβος με ένα παιδί: Μόλις διαγράψετε τον κόμβο, απλώς συνδέστε τον θυγατρικό του κόμβο με τον γονικό κόμβο της διαγραμμένης τιμής.
• Περίπτωση 3 – Κόμβος με δύο παιδιά: Αυτή είναι η πιο δύσκολη κατάσταση και λειτουργεί με βάση τους ακόλουθους δύο κανόνες:
  • 3α – Προκάτοχος κατά σειρά: πρέπει να διαγράψετε τον κόμβο με τα δύο θυγατρικά στοιχεία και να τον αντικαταστήσετε με τη μεγαλύτερη τιμή στο αριστερό υποδέντρο του διαγραμμένου κόμβου.
  • 3β – Διάδοχος κατά σειρά: πρέπει να διαγράψετε τον κόμβο με τα δύο θυγατρικά στοιχεία και να τον αντικαταστήσετε με τη μικρότερη τιμή στο δεξιό υποδέντρο του διαγραμμένου κόμβου.

1. Αυτή είναι η πρώτη περίπτωση διαγραφής, στην οποία διαγράφετε έναν κόμβο που δεν έχει θυγατρικά στοιχεία. Όπως μπορείτε να δείτε στο διάγραμμα, τα 19, 10 και 5 δεν έχουν θυγατρικά στοιχεία. Αλλά θα διαγράψουμε το 19.
2. Διαγράψτε την τιμή 19 και αφαιρέστε τη σύνδεση από τον κόμβο.
3. Δείτε τη νέα δομή του BST χωρίς το 19.

1. Αυτή είναι η δεύτερη περίπτωση διαγραφής, στην οποία διαγράφετε έναν κόμβο που έχει 1 θυγατρικό. Όπως μπορείτε να δείτε στο διάγραμμα, το 9 έχει ένα θυγατρικό.
2. Διαγράψτε τον κόμβο 9 και αντικαταστήστε τον με τον θυγατρικό του κόμβο 10 και προσθέστε έναν σύνδεσμο από τον 7 στον 10.
3. Δείτε τη νέα δομή του BST χωρίς το 9.

1. Εδώ θα διαγράψετε τον κόμβο 12 που έχει δύο θυγατρικά στοιχεία.
2. Η διαγραφή του κόμβου θα γίνει με βάση τον κανόνα της κατά σειρά προτεραιότητας, που σημαίνει ότι το μεγαλύτερο στοιχείο στο αριστερό υποδέντρο από τα 12 θα τον αντικαταστήσει.
3. Διαγράψτε τον κόμβο 12 και αντικαταστήστε τον με 10, καθώς είναι η μεγαλύτερη τιμή στο αριστερό υποδέντρο.
4. Δείτε τη νέα δομή του BST μετά τη διαγραφή του 12.

1. Διαγράψτε έναν κόμβο 12 που έχει δύο θυγατρικά στοιχεία.
2. Η διαγραφή του κόμβου θα γίνει με βάση τον κανόνα In-Order Successor, που σημαίνει ότι το μικρότερο στοιχείο στο δεξί υποδέντρο των 12 θα τον αντικαταστήσει.
3. Διαγράψτε τον κόμβο 12 και αντικαταστήστε τον με 19, καθώς είναι η μικρότερη τιμή στο δεξί υποδέντρο.
4. Δείτε τη νέα δομή του BST μετά τη διαγραφή του 12.

Παρατσούκλι Code για τη διαγραφή ενός κόμβου

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Σημαντικοί Όροι

• Εισάγετε: Εισάγει ένα στοιχείο σε ένα δέντρο / δημιουργεί ένα δέντρο.
• Έρευνα: Αναζητά ένα στοιχείο σε ένα δέντρο.
• Προπαραγγελία Ταξιδιού: Διασχίζει ένα δέντρο με τρόπο προπαραγγελίας.
• Διαδρομή σειράς: Διασχίζει ένα δέντρο με σωστή σειρά.
• Ταχυδρομική Διαδρομή Παραγγελίας: Διασχίζει ένα δέντρο με τρόπο που παραγγέλνεται μετά την παραγγελία.

Συχνές Ερωτήσεις