Συχνή Μοτίβα σε δέντρο Αλγόριθμοι

Τα δεδομένα συνήθως αποθηκεύονται σε δυαδική δομές δέντρων με τη χρήση εξειδικευμένων αλγορίθμων . Πολλά πλεονεκτήματα προέρχονται από την αποθήκευση δεδομένων σε μια δομή δέντρου . Για παράδειγμα, η αναζήτηση μια διατεταγμένη δυαδικό δέντρο είναι πολύ ταχύτερη από τη διαλογή μια διαδοχική δομή δεδομένων , όπως μία συστοιχία . Μια δενδροειδής δομή δεδομένων μπορεί να αναλάβει πολλούς τύπους μοντέλων κατά τη διάρκεια της πρόσβασης στα δεδομένα και τροποποίηση. Η κατανόηση αυτών των προτύπων μπορεί να σας βοηθήσει να σχεδιάσουμε καλύτερα αλγορίθμων για τη βελτιστοποίηση ενός αλγορίθμου δέντρο . Βασικές συνιστώσες ενός Binary Tree
Η

Ένα δυαδικό δέντρο αποτελείται από κόμβους που αποθηκεύουν τα δεδομένα και το σημείο σε άλλους κόμβους στο δέντρο . Ο κόμβος είναι το σημείο εκκίνησης του δέντρου και καταλαμβάνει το κορυφαίο επίπεδο . Μπορεί να έχει μέχρι δύο κόμβους του παιδιού . Αυτοί οι κόμβοι παιδί μπορεί επίσης να έχει μέχρι δύο κόμβους παιδί . Ο αριθμός των κόμβων του παιδιού από ένα δεδομένο κόμβο ονομάζεται ο βαθμός του κόμβου . Ένας κόμβος χωρίς παιδιά και ένας βαθμός μηδέν ονομάζεται φύλλο . Το μήκος σε κόμβους από τον κόμβο ρίζας προς το απώτατο κόμβο φύλλων είναι το ύψος του δέντρου. Το βάθος ενός κόμβου είναι η απόσταση από τον κόμβο ρίζας σε αυτό. Κάθε κόμβος που έχει το ίδιο βάθος λέγεται ότι είναι στο ίδιο επίπεδο . ΤΕΙ Θεσσαλονίκης Πλήρης Binary Tree
Η

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

Η Perfect Binary Tree
Η

Ένα τέλειο δυαδικό δέντρο έχει τις ίδιες ιδιότητες του πλήρες δυαδικό δέντρο , αλλά όλοι οι κόμβοι φύλλων βρίσκονται στο ίδιο επίπεδο , πράγμα που σημαίνει ότι το βάθος όλων των φύλλων είναι η ίδια σε ένα τέλειο δυαδικό δένδρο . Δεδομένου ότι είναι επίσης ένα πλήρες δυαδικό δέντρο , όλοι οι κόμβοι εκτός από τους κόμβους έχουν ένα βαθμό 2 .
Εικόνων Ισορροπημένη Binary Tree
Η

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

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