[Powered by Google Translate] Πώς θα εκπροσωπεί όλα τα μέλη της οικογένειάς σας σε έναν υπολογιστή; Θα μπορούσαμε να χρησιμοποιήσουμε απλά μια λίστα, αλλά υπάρχει μια σαφής ιεραρχία εδώ. 

Ας πούμε ότι αρχίζουμε με προγιαγιά σας, Alice. Έχει 2 γιους, ο Bob και ο παππούς σου, Τσάρλι. Τσάρλι έχει 3 παιδιά, Ο θείος σας, ο Dave, η θεία σου, η Εύα, και ο πατέρας σας, ο Φρεντ. Είστε μόνο παιδί του Fred. 

Γιατί θα οργάνωση τα μέλη της οικογένειας σας με αυτόν τον τρόπο να είναι καλύτερη από την απλή αναπαράσταση λίστα; Ένας λόγος είναι ότι αυτή η ιεραρχική δομή, που ονομάζεται «δέντρο», περιέχει περισσότερες πληροφορίες από ό, τι μια απλή λίστα. Γνωρίζουμε τις οικογενειακές σχέσεις μεταξύ όλων ακριβώς με την εξέταση το δέντρο. Επίσης, αυτό μπορεί να επιταχύνει look-up χρόνο παρά πολύ, αν τα δεδομένα είναι ταξινομημένο δέντρο. 

Δεν μπορούν να επωφεληθούν από αυτό εδώ, αλλά θα δούμε ένα παράδειγμα αυτό σύντομα. Κάθε άτομο αντιπροσωπεύεται από έναν κόμβο στο δέντρο. Οι κόμβοι μπορούν να έχουν το παιδί τους κόμβους καθώς και ένα μητρικό κόμβο. Αυτοί είναι οι τεχνικοί όροι, ακόμη και όταν χρησιμοποιούν τα δέντρα για πράγματα εκτός από τις οικογένειες. Κόμβο της Alice έχει 2 παιδιά και δεν τους γονείς, ενώ κόμβο του Τσάρλι έχει 3 παιδιά και 1 γονέα. 

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

Ένα δέντρο δυαδικό είναι ένα συγκεκριμένο είδος δέντρου, στο οποίο κάθε κόμβος έχει, στην καλύτερη περίπτωση, 2 παιδιά. Εδώ είναι η struct ενός κόμβου ενός δυαδικού δέντρου στο C. Κάθε κόμβος έχει κάποια δεδομένα που σχετίζονται με το και 2 δείκτες σε άλλους κόμβους. 

Στο οικογενειακό μας δέντρο, τα δεδομένα που σχετίζονται ήταν το όνομα του κάθε ατόμου. Εδώ είναι ένα int, αν και θα μπορούσε να είναι οτιδήποτε. Όπως αποδεικνύεται, ένα δυαδικό δέντρο δεν θα ήταν μια καλή παράσταση για μια οικογένεια, δεδομένου ότι οι άνθρωποι έχουν συχνά περισσότερα από 2 παιδιά. 

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

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

Αυτό είναι το πώς θα φαινόταν αν γυρίσαμε όλους τους κόμβους σε C structs. Παρατηρήστε ότι αν ένα παιδί λείπει, ο δείκτης είναι μηδενική. Πώς να ελέγξετε αν 7 είναι στο δέντρο; Ξεκινάμε από τη ρίζα. Επτά είναι μεγαλύτερος από 6, οπότε αν είναι στο δέντρο, θα πρέπει να είναι προς τα δεξιά. Στη συνέχεια, είναι μικρότερο από 8, και έτσι πρέπει να μείνει. Εδώ, έχουμε βρει 7. Τώρα, θα ελέγξουμε για 5. Πέντε είναι μικρότερο από 6, έτσι ώστε να πρέπει να είναι προς τα αριστερά. Πέντε είναι μεγαλύτερο από 2, γι 'αυτό πρέπει να είναι σωστό, και είναι επίσης μεγαλύτερος από 4, οπότε πρέπει να είναι σωστό και πάλι. Ωστόσο, δεν υπάρχει κανένα παιδί εδώ. Ο δείκτης είναι μηδενική. Αυτό σημαίνει ότι δεν είναι 5 στο δέντρο μας. 

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

Να θυμάστε ότι το 5 δεν ήταν στο δέντρο. Πώς μπορούμε να το τοποθετήσετε; Η διαδικασία μοιάζει με την αναζήτηση. Έχουμε επαναλάβει κάτω από το δέντρο αρχίζει από 6, αριστερά προς 2, δικαίωμα 4, και πάλι δεξιά, αλλά το 4 δεν έχει παιδί σε αυτή την πλευρά. Αυτή θα είναι η νέα θέση για 5, και θα αρχίσει χωρίς παιδιά. 

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

Για παράδειγμα, η ακόλουθη είναι μια έγκυρη δένδρο δυαδική αναζήτηση. Ωστόσο, αν προσπαθήσουμε να βρούμε 9, έχουμε να διασχίσουν κάθε κόμβο. Δεν είναι καλύτερη από μια συνδεδεμένη λίστα. Ιδανικά, θα θέλαμε σε κάθε κόμβο του δέντρου δυαδική αναζήτηση μας να έχουν 2 παιδιά. Με αυτό τον τρόπο, εισαγωγή, διαγραφή και αναζήτηση θα λάβει, στη χειρότερη περίπτωση, O (log n) χρόνο. Το δέντρο από πριν θα μπορούσε να είναι πιο ισορροπημένη, όπως αυτό. Τώρα, κοιτώντας ψηλά οποιαδήποτε αξία έχει, το πολύ, 3 βήματα. Αυτό το δέντρο είναι ισορροπημένη, έννοια που έχει ένα ελάχιστο βάθος σε σχέση με τον αριθμό των κόμβων. 

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

Το όνομά μου είναι Bannus Van der Kloot. Αυτό είναι CS50.