Δυαδικό δέντρο αναζήτησης (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, επιστρέφουν την τιμή στον χρήστη.

Ψευδοκώδικας για αναζήτηση στο 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 Κόμβος με δύο παιδιά: αυτή είναι η πιο δύσκολη κατάσταση και λειτουργεί με τους ακόλουθους δύο κανόνες
• 3a – In Order Predecessor: πρέπει να διαγράψετε τον κόμβο με δύο παιδιά και να τον αντικαταστήσετε με τη μεγαλύτερη τιμή στο αριστερό υποδέντρο του διαγραμμένου κόμβου
• 3b – In Order Successor: πρέπει να διαγράψετε τον κόμβο με δύο παιδιά και να τον αντικαταστήσετε με τη μεγαλύτερη τιμή στο δεξί υποδέντρο του διαγραμμένου κόμβου

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

Ψευδοκώδικας για τη διαγραφή ενός κόμβου

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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

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

• Εισαγωγή: Εισαγωγή στοιχείου σε δέντρο/δημιουργία δέντρου.
• Αναζήτηση: Αναζητά ένα στοιχείο σε ένα δέντρο.
• Preorder Traversal: Διασχίζει ένα δέντρο με τρόπο προπαραγγελίας.
• Inorder Traversal: Διασχίζει ένα δέντρο με έναν τρόπο.
• Postorder Traversal: Διασχίζει ένα δέντρο με τρόπο μετά την παραγγελία.

Σύνοψη

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