Τα κόκκινα-μαύρα δέντρα: επισκόπηση, χαρακτηριστικά

Rudolph Bayer έχει αναπτύξει ένα σύστημα «κόκκινα-μαύρα δέντρα» στις αρχές της δεκαετίας του 1970. Το όνομα αυτής της δόθηκε Gimpas L. και R. Sedgewick.

Τι ένα κόκκινο-μαύρα δέντρα

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

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

Η εμφάνιση του όρου

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

εφαρμογή

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

Δυνατόν να δημιουργηθεί ένα κόκκινο-μαύρο δέντρο σε Actionscript, Python, C ++, και σχεδόν οποιαδήποτε άλλη γλώσσα προγραμματισμού. Είναι πολύ απλό. Ένα κόκκινο-μαύρο δέντρο της Java είναι επίσης αρκετά διαδεδομένη.

χαρακτηριστικά

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

• κόμβο χρώμα είναι αποκλειστικά ένα από τα δύο παραπάνω. Δεν υπάρχουν άλλες επιλογές, είναι επίσης αντανακλάται στο όνομα του όρου.
• Η ρίζα του δέντρου πρέπει πάντα να είναι βαμμένο μαύρο. Εξαιρέσεις είναι δυνατές, αλλά μια τέτοια απόκλιση από τον κανόνα προσθέτει ο κίνδυνος που λοξοδρόμησή αυτο-εξισορρόπησης δέντρο.
• Όλα τα φύλλα έχουν μια τιμή μηδέν (ΜΗΔΕΝ) και σημειώνονται με μαύρο.
• Πρέπει να λαμβάνεται μέριμνα ώστε οι δύο απόγονοι του κάθε κόκκινου κόμβου είναι μαύρο γονέα.
• Κάθε διαδρομή φως από ένα συγκεκριμένο κόμβο σε κάθε κόμβο-φύλλο του παιδιού παρέχει ακριβώς ίσο με τον αριθμό των μαύρων μονάδων.

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

Γιατί να επιλέξετε ένα κόκκινο-μαύρα δέντρα

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

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

Για παράδειγμα, αν τους συγκρίνουμε με την τέλεια ισορροπία στο βαθμό δέντρα τους, μια κατάσταση μπορεί να προκύψει όταν παρατήρησε ότι οι «ιδανικές» εκπρόσωποι επιβάλλουν υπερβολικά ασυμβίβαστες απαιτήσεις. Και από την άποψη της υλοποίησης της δράσης κατάργηση του δέντρου ή εξαπλωθεί πάρα πολύ χρόνο και προσπάθεια δαπανώνται για τη σταθεροποίηση της κατάστασης στη σωστή ισορροπία.

διαδικασίες

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

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

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

Περαιτέρω δράσεις μας είναι άμεσα εξαρτάται από το χρώμα των γειτονικών κόμβων. ο όρος «θείος» χρησιμοποιείται γι 'αυτούς. Η άμεση αναλογία με το οικογενειακό δέντρο. Ως εκ τούτου:

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

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

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