Κόκκινο-μαύρο δέντρο: Δυαδικά δέντρα δυαδικής αναζήτησης που εξηγούνται με παραδείγματα

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

Το Κόκκινο-Μαύρο Δέντρο είναι ένας τύπος δέντρου δυαδικής αναζήτησης (BST). Σε ένα κόκκινο-μαύρο δέντρο, κάθε κόμβος ακολουθεί αυτούς τους κανόνες:

  1. Κάθε κόμβος έχει δύο παιδιά, χρωματισμένα είτε κόκκινα είτε μαύρα.
  2. Κάθε κόμβος φύλλων δέντρων είναι πάντα μαύρος.
  3. Κάθε κόκκινος κόμβος έχει και τα δύο παιδιά του μαύρο.
  4. Δεν υπάρχουν δύο γειτονικοί κόκκινοι κόμβοι (Ένας κόκκινος κόμβος δεν μπορεί να έχει κόκκινο γονέα ή κόκκινο παιδί).
  5. Κάθε διαδρομή από τη ρίζα προς έναν κόμβο φύλλων δέντρων έχει τον ίδιο αριθμό μαύρων κόμβων (ονομάζεται "μαύρο ύψος").

Εισαγωγή σε κόκκινα-μαύρα δέντρα

Ένας κόμβος αρχικά εισάγεται σε ένα Κόκκινο-Μαύρο Δέντρο, όπως κάθε Δυαδικό Δέντρο Αναζήτησης. Στη συνέχεια, ο νέος κόμβος δίνει ένα κόκκινο χρώμα. Μετά την εισαγωγή αυτού του κόμβου, το δέντρο πρέπει να επικυρωθεί για να διασφαλιστεί ότι καμία από τις πέντε ιδιότητες δεν έχει παραβιαστεί. Εάν μια ιδιότητα έχει παραβιαστεί, υπάρχουν τρεις πιθανές περιπτώσεις που απαιτούν είτε αριστερή περιστροφή, δεξιά περιστροφή ή / και επαναχρωματισμό των κόμβων. Οι περιπτώσεις εξαρτώνται από τον "θείο" του τρέχοντος κόμβου. Συγκεκριμένα, εάν ο κόμβος "θείος" είναι μαύρος ή κόκκινος. Για περισσότερες πληροφορίες σχετικά με την εισαγωγή, μπορείτε να βρείτε τις τρεις περιπτώσεις εδώ.

Κόκκινο-Μαύρο δέντρο αριστερά

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

Ιδιότητες των Αριστερών Κλίσεων Κόκκινα-Μαύρα Δέντρα

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

Συγκεκριμένα, σε ένα αριστερόπλευρο κόκκινο-μαύρο 2-3 δέντρο χτισμένο από N τυχαία πλήκτρα: -> Μια τυχαία επιτυχημένη αναζήτηση εξετάζει log2 N- 0,5 κόμβους. -> Το μέσο ύψος του δέντρου είναι περίπου2 log2 N