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

Σε αυτό το σεμινάριο, θα μάθετε τι είναι ένα κόκκινο-μαύρο δέντρο. Επίσης, θα βρείτε λειτουργικά παραδείγματα διαφόρων λειτουργιών που εκτελούνται σε ένα κόκκινο-μαύρο δέντρο σε C, C ++, Java και Python.

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

Ένα κόκκινο-μαύρο δέντρο ικανοποιεί τις ακόλουθες ιδιότητες:

  1. Κόκκινη / Μαύρη ιδιότητα: Κάθε κόμβος είναι χρωματισμένος, είτε κόκκινος είτε μαύρος.
  2. Ιδιότητα ρίζας: Η ρίζα είναι μαύρη.
  3. Ιδιότητα φύλλων: Κάθε φύλλο (ΜΗΝ) είναι μαύρο.
  4. Κόκκινη ιδιότητα: Εάν ένας κόμβος έχει παιδιά τότε, τα παιδιά είναι πάντα μαύρα.
  5. Ιδιότητα βάθους: Για κάθε κόμβο, οποιαδήποτε απλή διαδρομή από αυτόν τον κόμβο σε οποιοδήποτε φύλλο απογόνου έχει το ίδιο μαύρο βάθος (ο αριθμός των μαύρων κόμβων).

Ένα παράδειγμα ενός κόκκινου-μαύρου δέντρου είναι:

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

Κάθε κόμβος έχει τα ακόλουθα χαρακτηριστικά:

  • χρώμα
  • κλειδί
  • αριστερά παιδιά
  • δεξιά Παιδί
  • γονικός (εκτός από τον ριζικό κόμβο)

Πώς το κόκκινο-μαύρο δέντρο διατηρεί την ιδιότητα της αυτο-εξισορρόπησης;

Το κόκκινο-μαύρο χρώμα προορίζεται για την εξισορρόπηση του δέντρου.

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

Λειτουργίες σε ένα κόκκινο-μαύρο δέντρο

Διάφορες λειτουργίες που μπορούν να εκτελεστούν σε ένα κόκκινο-μαύρο δέντρο είναι:

Περιστροφή των υποδέντρων σε ένα κόκκινο-μαύρο δέντρο

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

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

Υπάρχουν δύο τύποι περιστροφών:

Αριστερή περιστροφή

Στην αριστερή περιστροφή, η διάταξη των κόμβων στα δεξιά μετατρέπεται σε διευθετήσεις στον αριστερό κόμβο.

Αλγόριθμος

  1. Αφήστε το αρχικό δέντρο να είναι: Αρχικό δέντρο
  2. Εάν το y έχει ένα αριστερό υποδένδρο, αντιστοιχίστε το x ως γονικό στοιχείο του αριστερού υποδέντρου του y Αντιστοιχίστε το x ως γονέα του αριστερού δευτερεύοντος δέντρου του y
  3. Εάν ο γονέας του x είναι NULL, ορίστε το y ως τη ρίζα του δέντρου.
  4. Διαφορετικά, αν το x είναι το αριστερό παιδί του p, κάντε το y ως το αριστερό παιδί του p.
  5. Αλλιώς ορίστε y ως το σωστό παιδί της σελ. Αλλάξτε το γονικό του x σε αυτό του y
  6. Κάντε y ως γονέα του x. Αντιστοιχίστε το y ως το γονικό του x.

Δεξιά περιστροφή

Στην δεξιά περιστροφή, η διάταξη των κόμβων στα αριστερά μετατρέπεται σε διευθετήσεις στον δεξιό κόμβο.

  1. Αφήστε το αρχικό δέντρο να είναι: Αρχικό δέντρο
  2. Εάν το x έχει ένα σωστό υποδένδρο, εκχωρήστε το y ως το γονικό του σωστού υποδέντρου του x Αντιστοιχίστε το y ως το γονικό του σωστού δευτερεύοντος δέντρου του x
  3. Εάν ο γονέας του y είναι NULL, κάντε το x ως τη ρίζα του δέντρου.
  4. Διαφορετικά εάν το y είναι το σωστό παιδί του γονέα του p, κάντε το x ως το σωστό παιδί του p.
  5. Αλλιώς ορίστε το x ως το αριστερό παιδί του σελ. Αντιστοιχίστε τον γονέα του y ως τον γονέα του x
  6. Κάντε το x ως γονέα του y. Αντιστοιχίστε το x ως γονέα του y

Περιστροφή αριστερά-δεξιά και δεξιά-αριστερά

Στην περιστροφή αριστερά-δεξιά, οι ρυθμίσεις μετατοπίζονται πρώτα προς τα αριστερά και μετά προς τα δεξιά.

  1. Κάντε αριστερή περιστροφή στο xy. Αριστερή περιστροφή xy
  2. Κάντε τη σωστή περιστροφή στο yz. Περιστρέψτε δεξιά zy

Στην περιστροφή δεξιά-αριστερά, οι ρυθμίσεις μετατοπίζονται πρώτα προς τα δεξιά και μετά προς τα αριστερά.

  1. Κάντε σωστή περιστροφή στο xy. Περιστρέψτε δεξιά xy
  2. Κάντε αριστερή περιστροφή στο zy. Αριστερή περιστροφή zy

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

Κατά την εισαγωγή ενός νέου κόμβου, ο νέος κόμβος εισάγεται πάντα ως ΚΟΚΚΙΝΟΣ κόμβος. Μετά την εισαγωγή ενός νέου κόμβου, εάν το δέντρο παραβιάζει τις ιδιότητες του κόκκινου-μαύρου δέντρου τότε, κάνουμε τις ακόλουθες λειτουργίες.

  1. Χρωματίζω πάλιν
  2. Περιστροφή

Αλγόριθμος για εισαγωγή ενός κόμβου

Ακολουθούνται τα ακόλουθα βήματα για την εισαγωγή ενός νέου στοιχείου σε ένα κόκκινο-μαύρο δέντρο:

  1. Ας γίνουμε το φύλλο (δηλ. NIL) Και x να είναι η ρίζα του δέντρου.
  2. Ελέγξτε εάν το δέντρο είναι κενό (δηλ. Αν το x είναι NIL). Εάν ναι, εισαγάγετε το νέοNode ως ριζικό κόμβο και χρωματίστε το μαύρο.
  3. Διαφορετικά, επαναλάβετε τα βήματα ακολουθώντας τα βήματα έως ότου NILεπιτευχθεί το φύλλο ( ).
    1. Συγκρίνετε το newKey με το rootKey.
    2. Εάν το newKey είναι μεγαλύτερο από το rootKey, διασχίστε το σωστό υποδένδρο.
    3. Διαφορετικά διασχίζετε το αριστερό υπόστρωμα.
  4. Αντιστοιχίστε τον γονέα του φύλλου ως γονέα του newNode.
  5. Εάν το leafKey είναι μεγαλύτερο από το newKey, κάντε το newNode ως rightChild.
  6. Διαφορετικά, κάντε το newNode ως leftChild.
  7. Αντιστοίχιση NULLπρος τα αριστερά και δεξιάChild του newNode.
  8. Αντιστοιχίστε το ΚΟΚΚΙΝΟ χρώμα στο newNode.
  9. Καλέστε τον αλγόριθμο InsertFix για να διατηρήσετε την ιδιότητα του κόκκινου-μαύρου δέντρου εάν παραβιαστεί.

Γιατί οι νεοσύστατοι κόμβοι είναι πάντα κόκκινοι σε ένα κόκκινο-μαύρο δέντρο;

Αυτό συμβαίνει επειδή η εισαγωγή κόκκινου κόμβου δεν παραβιάζει την ιδιότητα βάθους ενός κόκκινου-μαύρου δέντρου.

Εάν επισυνάψετε έναν κόκκινο κόμβο σε έναν κόκκινο κόμβο, τότε ο κανόνας παραβιάζεται, αλλά είναι πιο εύκολο να διορθώσετε αυτό το πρόβλημα από το πρόβλημα που παρουσιάστηκε παραβιάζοντας την ιδιότητα βάθους.

Αλγόριθμος για τη διατήρηση της κόκκινης-μαύρης ιδιότητας μετά την εισαγωγή

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

  1. Κάντε τα εξής ενώ ο γονέας του newNode p είναι ΚΟΚΚΙΝΟΣ.
  2. Εάν το p είναι το αριστερό παιδί του grandParent gP του z, κάντε τα εξής.
    Περίπτωση-I:
    1. Εάν το χρώμα του σωστού παιδιού της gP του z είναι ΚΟΚΚΙΝΟ, ορίστε το χρώμα και των δύο παιδιών της gP ως ΜΑΥΡΟ και του χρώματος της gP ως ΚΟΚΚΙΝΟ.
    2. Εκχωρήστε το gP στο newNode.
      Περίπτωση II:
    3. Διαφορετικά, αν το newNode είναι το σωστό παιδί του p τότε, αντιστοιχίστε το p στο newNode.
    4. Αριστερή περιστροφή newNode.
      Υπόθεση-III:
    5. Ορίστε το χρώμα του p ως ΜΑΥΡΟ και το χρώμα του gP ως ΚΟΚΚΙΝΟ.
    6. Περιστροφή δεξιά gP.
  3. Αλλιώς, κάντε τα εξής.
    1. Εάν το χρώμα του αριστερού παιδιού του gP του z είναι ΚΟΚΚΙΝΟ, ορίστε το χρώμα και των δύο παιδιών του gP ως ΜΑΥΡΟ και του χρώματος του gP ως ΚΟΚΚΙΝΟ.
    2. Εκχωρήστε το gP στο newNode.
    3. Διαφορετικά, αν το newNode είναι το αριστερό παιδί του p τότε, αντιστοιχίστε το p στο newNode και το Right-Rotate newNode.
    4. Ορίστε το χρώμα του p ως ΜΑΥΡΟ και το χρώμα του gP ως ΚΟΚΚΙΝΟ.
    5. Αριστερή περιστροφή gP.
  4. Ορίστε τη ρίζα του δέντρου ως ΜΑΥΡΟ.

Διαγραφή ενός στοιχείου από ένα κόκκινο-μαύρο δέντρο

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

Αλγόριθμος για διαγραφή ενός κόμβου

  1. Αποθηκεύστε το χρώμα του κόμβουToBeDeleted σε origrinalColor.
  2. Εάν το αριστερό παιδί του nodeToBeDeleted είναι NULL
    1. Αντιστοιχίστε το σωστό παιδί του κόμβουToBeDeleted στο x.
    2. Μεταμόσχευση κόμβου ToBe Διαγράφεται με x.
  3. Διαφορετικά, εάν είναι το σωστό παιδί του nodeToBeDeleted NULL
    1. Αντιστοιχίστε το αριστερό παιδί του κόμβουToBeDeleted σε x.
    2. Μεταμόσχευση κόμβου ToBe Διαγράφεται με x.
  4. Αλλού
    1. Αντιστοιχίστε το ελάχιστο δεξί υπότιτλο του noteToBeDeleted σε y.
    2. Αποθηκεύστε το χρώμα του y στο originalColor.
    3. Αντιστοιχίστε το δεξί παιδί του y σε x.
    4. Εάν το y είναι θυγατρικό του nodeToBeDeleted, ορίστε τον γονέα του x ως y.
    5. Αλλιώς, μεταμοσχεύστε y με δεξιά Παιδί y.
    6. Μεταμόσχευση κόμβου ToBe Διαγράφεται με y.
    7. Ορίστε το χρώμα του y με το αρχικόColor.
  5. Εάν το originalColor είναι ΜΑΥΡΟ, καλέστε το DeleteFix (x).

Αλγόριθμος για τη διατήρηση της ιδιότητας Red-Black μετά τη διαγραφή

Αυτός ο αλγόριθμος εφαρμόζεται όταν ένας μαύρος κόμβος διαγράφεται επειδή παραβιάζει την ιδιότητα μαύρου βάθους του κόκκινου-μαύρου δέντρου.

Αυτή η παραβίαση διορθώνεται υποθέτοντας ότι ο κόμβος x (που καταλαμβάνει την αρχική θέση του y) έχει ένα επιπλέον μαύρο. Αυτό καθιστά τον κόμβο x ούτε κόκκινο ούτε μαύρο. Είναι διπλά μαύρο ή μαύρο και κόκκινο. Αυτό παραβιάζει τις ιδιότητες κόκκινου-μαύρου.

Ωστόσο, το χαρακτηριστικό χρώματος του x δεν αλλάζει, αλλά το επιπλέον μαύρο αντιπροσωπεύεται στο x που δείχνει στον κόμβο.

Το επιπλέον μαύρο μπορεί να αφαιρεθεί εάν

  1. Φτάνει στον ριζικό κόμβο.
  2. Εάν το x δείχνει έναν κόκκινο-μαύρο κόμβο. Σε αυτήν την περίπτωση, το x είναι μαύρο.
  3. Πραγματοποιούνται κατάλληλες περιστροφές και επαναχρωματισμός.

Ο ακόλουθος αλγόριθμος διατηρεί τις ιδιότητες ενός κόκκινου-μαύρου δέντρου.

  1. Κάντε τα εξής έως ότου το x δεν είναι η ρίζα του δέντρου και το χρώμα του x είναι ΜΑΥΡΟ
  2. Εάν το x είναι το αριστερό παιδί του γονέα του τότε,
    1. Εκχώρηση w στο αδερφό του x.
    2. Εάν το σωστό παιδί του γονέα του x είναι ΚΟΚΚΙΝΟ,
      Περίπτωση I:
      1. Ορίστε το χρώμα του σωστού παιδιού του γονέα του x ως ΜΑΥΡΟ.
      2. Ορίστε το χρώμα του γονικού του x ως ΚΟΚΚΙΝΟ.
      3. Αριστερή περιστροφή του γονέα του x.
      4. Αντιστοιχίστε το rightChild του γονέα του x στο w.
    3. Εάν το χρώμα τόσο του δεξιού όσο και του αριστερούΤο παιδί του w είναι ΜΑΥΡΟ,
      Περίπτωση II
      1. Ορίστε το χρώμα του w ως ΚΟΚΚΙΝΟ
      2. Αντιστοιχίστε τον γονέα του x στο x.
    4. Διαφορετικά, εάν το χρώμα του δεξιού Παιδί του w είναι BLACK
      Case-III:
      1. Ορίστε το χρώμα του αριστερού παιδιού w ως ΜΑΥΡΟ
      2. Ορίστε το χρώμα του w ως ΚΟΚΚΙΝΟ
      3. Περιστροφή δεξιά w.
      4. Αντιστοιχίστε το rightChild του γονέα του x στο w.
    5. Εάν δεν εμφανιστεί κάποια από τις παραπάνω περιπτώσεις, κάντε τα εξής.
      Υπόθεση-IV:
      1. Ορίστε το χρώμα του w ως το χρώμα του γονέα του x.
      2. Ορίστε το χρώμα του γονέα του x ως ΜΑΥΡΟ.
      3. Ορίστε το χρώμα του σωστού παιδιού του W ως ΜΑΥΡΟ.
      4. Αριστερή περιστροφή του γονέα του x.
      5. Ορίστε το x ως τη ρίζα του δέντρου.
  3. Αλλιώς το ίδιο όπως παραπάνω με το δικαίωμα να αλλάζει στα αριστερά και το αντίστροφο
  4. Ορίστε το χρώμα του x ως ΜΑΥΡΟ.

Ανατρέξτε στις λειτουργίες εισαγωγής και διαγραφής για περισσότερες εξηγήσεις με παραδείγματα.

Παραδείγματα Python, Java και C / C ++

Python Java C C ++ 
 # Implementing Red-Black Tree in Python import sys # Node creation class Node(): def __init__(self, item): self.item = item self.parent = None self.left = None self.right = None self.color = 1 class RedBlackTree(): def __init__(self): self.TNULL = Node(0) self.TNULL.color = 0 self.TNULL.left = None self.TNULL.right = None self.root = self.TNULL # Preorder def pre_order_helper(self, node): if node != TNULL: sys.stdout.write(node.item + " ") self.pre_order_helper(node.left) self.pre_order_helper(node.right) # Inorder def in_order_helper(self, node): if node != TNULL: self.in_order_helper(node.left) sys.stdout.write(node.item + " ") self.in_order_helper(node.right) # Postorder def post_order_helper(self, node): if node != TNULL: self.post_order_helper(node.left) self.post_order_helper(node.right) sys.stdout.write(node.item + " ") # Search the tree def search_tree_helper(self, node, key): if node == TNULL or key == node.item: return node if key < node.item: return self.search_tree_helper(node.left, key) return self.search_tree_helper(node.right, key) # Balancing the tree after deletion def delete_fix(self, x): while x != self.root and x.color == 0: if x == x.parent.left: s = x.parent.right if s.color == 1: s.color = 0 x.parent.color = 1 self.left_rotate(x.parent) s = x.parent.right if s.left.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.right.color == 0: s.left.color = 0 s.color = 1 self.right_rotate(s) s = x.parent.right s.color = x.parent.color x.parent.color = 0 s.right.color = 0 self.left_rotate(x.parent) x = self.root else: s = x.parent.left if s.color == 1: s.color = 0 x.parent.color = 1 self.right_rotate(x.parent) s = x.parent.left if s.right.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.left.color == 0: s.right.color = 0 s.color = 1 self.left_rotate(s) s = x.parent.left s.color = x.parent.color x.parent.color = 0 s.left.color = 0 self.right_rotate(x.parent) x = self.root x.color = 0 def __rb_transplant(self, u, v): if u.parent == None: self.root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v v.parent = u.parent # Node deletion def delete_node_helper(self, node, key): z = self.TNULL while node != self.TNULL: if node.item == key: z = node if node.item <= key: node = node.right else: node = node.left if z == self.TNULL: print("Cannot find key in the tree") return y = z y_original_color = y.color if z.left == self.TNULL: x = z.right self.__rb_transplant(z, z.right) elif (z.right == self.TNULL): x = z.left self.__rb_transplant(z, z.left) else: y = self.minimum(z.right) y_original_color = y.color x = y.right if y.parent == z: x.parent = y else: self.__rb_transplant(y, y.right) y.right = z.right y.right.parent = y self.__rb_transplant(z, y) y.left = z.left y.left.parent = y y.color = z.color if y_original_color == 0: self.delete_fix(x) # Balance the tree after insertion def fix_insert(self, k): while k.parent.color == 1: if k.parent == k.parent.parent.right: u = k.parent.parent.left if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.left: k = k.parent self.right_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.left_rotate(k.parent.parent) else: u = k.parent.parent.right if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.right: k = k.parent self.left_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.right_rotate(k.parent.parent) if k == self.root: break self.root.color = 0 # Printing the tree def __print_helper(self, node, indent, last): if node != self.TNULL: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " s_color = "RED" if node.color == 1 else "BLACK" print(str(node.item) + "(" + s_color + ")") self.__print_helper(node.left, indent, False) self.__print_helper(node.right, indent, True) def preorder(self): self.pre_order_helper(self.root) def inorder(self): self.in_order_helper(self.root) def postorder(self): self.post_order_helper(self.root) def searchTree(self, k): return self.search_tree_helper(self.root, k) def minimum(self, node): while node.left != self.TNULL: node = node.left return node def maximum(self, node): while node.right != self.TNULL: node = node.right return node def successor(self, x): if x.right != self.TNULL: return self.minimum(x.right) y = x.parent while y != self.TNULL and x == y.right: x = y y = y.parent return y def predecessor(self, x): if (x.left != self.TNULL): return self.maximum(x.left) y = x.parent while y != self.TNULL and x == y.left: x = y y = y.parent return y def left_rotate(self, x): y = x.right x.right = y.left if y.left != self.TNULL: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def right_rotate(self, x): y = x.left x.left = y.right if y.right != self.TNULL: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def insert(self, key): node = Node(key) node.parent = None node.item = key node.left = self.TNULL node.right = self.TNULL node.color = 1 y = None x = self.root while x != self.TNULL: y = x if node.item < x.item: x = x.left else: x = x.right node.parent = y if y == None: self.root = node elif node.item < y.item: y.left = node else: y.right = node if node.parent == None: node.color = 0 return if node.parent.parent == None: return self.fix_insert(node) def get_root(self): return self.root def delete_node(self, item): self.delete_node_helper(self.root, item) def print_tree(self): self.__print_helper(self.root, "", True) if __name__ == "__main__": bst = RedBlackTree() bst.insert(55) bst.insert(40) bst.insert(65) bst.insert(60) bst.insert(75) bst.insert(57) bst.print_tree() print("After deleting an element") bst.delete_node(40) bst.print_tree() 
 // Implementing Red-Black Tree in Java class Node ( int data; Node parent; Node left; Node right; int color; ) public class RedBlackTree ( private Node root; private Node TNULL; // Preorder private void preOrderHelper(Node node) ( if (node != TNULL) ( System.out.print(node.data + " "); preOrderHelper(node.left); preOrderHelper(node.right); ) ) // Inorder private void inOrderHelper(Node node) ( if (node != TNULL) ( inOrderHelper(node.left); System.out.print(node.data + " "); inOrderHelper(node.right); ) ) // Post order private void postOrderHelper(Node node) ( if (node != TNULL) ( postOrderHelper(node.left); postOrderHelper(node.right); System.out.print(node.data + " "); ) ) // Search the tree private Node searchTreeHelper(Node node, int key) ( if (node == TNULL || key == node.data) ( return node; ) if (key < node.data) ( return searchTreeHelper(node.left, key); ) return searchTreeHelper(node.right, key); ) // Balance the tree after deletion of a node private void fixDelete(Node x) ( Node s; while (x != root && x.color == 0) ( if (x == x.parent.left) ( s = x.parent.right; if (s.color == 1) ( s.color = 0; x.parent.color = 1; leftRotate(x.parent); s = x.parent.right; ) if (s.left.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.right.color == 0) ( s.left.color = 0; s.color = 1; rightRotate(s); s = x.parent.right; ) s.color = x.parent.color; x.parent.color = 0; s.right.color = 0; leftRotate(x.parent); x = root; ) ) else ( s = x.parent.left; if (s.color == 1) ( s.color = 0; x.parent.color = 1; rightRotate(x.parent); s = x.parent.left; ) if (s.right.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.left.color == 0) ( s.right.color = 0; s.color = 1; leftRotate(s); s = x.parent.left; ) s.color = x.parent.color; x.parent.color = 0; s.left.color = 0; rightRotate(x.parent); x = root; ) ) ) x.color = 0; ) private void rbTransplant(Node u, Node v) ( if (u.parent == null) ( root = v; ) else if (u == u.parent.left) ( u.parent.left = v; ) else ( u.parent.right = v; ) v.parent = u.parent; ) private void deleteNodeHelper(Node node, int key) ( Node z = TNULL; Node x, y; while (node != TNULL) ( if (node.data == key) ( z = node; ) if (node.data <= key) ( node = node.right; ) else ( node = node.left; ) ) if (z == TNULL) ( System.out.println("Couldn't find key in the tree"); return; ) y = z; int yOriginalColor = y.color; if (z.left == TNULL) ( x = z.right; rbTransplant(z, z.right); ) else if (z.right == TNULL) ( x = z.left; rbTransplant(z, z.left); ) else ( y = minimum(z.right); yOriginalColor = y.color; x = y.right; if (y.parent == z) ( x.parent = y; ) else ( rbTransplant(y, y.right); y.right = z.right; y.right.parent = y; ) rbTransplant(z, y); y.left = z.left; y.left.parent = y; y.color = z.color; ) if (yOriginalColor == 0) ( fixDelete(x); ) ) // Balance the node after insertion private void fixInsert(Node k) ( Node u; while (k.parent.color == 1) ( if (k.parent == k.parent.parent.right) ( u = k.parent.parent.left; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.left) ( k = k.parent; rightRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; leftRotate(k.parent.parent); ) ) else ( u = k.parent.parent.right; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.right) ( k = k.parent; leftRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; rightRotate(k.parent.parent); ) ) if (k == root) ( break; ) ) root.color = 0; ) private void printHelper(Node root, String indent, boolean last) ( if (root != TNULL) ( System.out.print(indent); if (last) ( System.out.print("R----"); indent += " "; ) else ( System.out.print("L----"); indent += "| "; ) String sColor = root.color == 1 ? "RED" : "BLACK"; System.out.println(root.data + "(" + sColor + ")"); printHelper(root.left, indent, false); printHelper(root.right, indent, true); ) ) public RedBlackTree() ( TNULL = new Node(); TNULL.color = 0; TNULL.left = null; TNULL.right = null; root = TNULL; ) public void preorder() ( preOrderHelper(this.root); ) public void inorder() ( inOrderHelper(this.root); ) public void postorder() ( postOrderHelper(this.root); ) public Node searchTree(int k) ( return searchTreeHelper(this.root, k); ) public Node minimum(Node node) ( while (node.left != TNULL) ( node = node.left; ) return node; ) public Node maximum(Node node) ( while (node.right != TNULL) ( node = node.right; ) return node; ) public Node successor(Node x) ( if (x.right != TNULL) ( return minimum(x.right); ) Node y = x.parent; while (y != TNULL && x == y.right) ( x = y; y = y.parent; ) return y; ) public Node predecessor(Node x) ( if (x.left != TNULL) ( return maximum(x.left); ) Node y = x.parent; while (y != TNULL && x == y.left) ( x = y; y = y.parent; ) return y; ) public void leftRotate(Node x) ( Node y = x.right; x.right = y.left; if (y.left != TNULL) ( y.left.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.left) ( x.parent.left = y; ) else ( x.parent.right = y; ) y.left = x; x.parent = y; ) public void rightRotate(Node x) ( Node y = x.left; x.left = y.right; if (y.right != TNULL) ( y.right.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.right) ( x.parent.right = y; ) else ( x.parent.left = y; ) y.right = x; x.parent = y; ) public void insert(int key) ( Node node = new Node(); node.parent = null; node.data = key; node.left = TNULL; node.right = TNULL; node.color = 1; Node y = null; Node x = this.root; while (x != TNULL) ( y = x; if (node.data < x.data) ( x = x.left; ) else ( x = x.right; ) ) node.parent = y; if (y == null) ( root = node; ) else if (node.data < y.data) ( y.left = node; ) else ( y.right = node; ) if (node.parent == null) ( node.color = 0; return; ) if (node.parent.parent == null) ( return; ) fixInsert(node); ) public Node getRoot() ( return this.root; ) public void deleteNode(int data) ( deleteNodeHelper(this.root, data); ) public void printTree() ( printHelper(this.root, "", true); ) public static void main(String() args) ( RedBlackTree bst = new RedBlackTree(); bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); System.out.println("After deleting:"); bst.deleteNode(40); bst.printTree(); ) )
 // Implementing Red-Black Tree in C #include #include enum nodeColor ( RED, BLACK ); struct rbNode ( int data, color; struct rbNode *link(2); ); struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) ( struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link(0) = newnode->link(1) = NULL; return newnode; ) // Insert an node void insertion(int data) ( struct rbNode *stack(98), *ptr, *newnode, *xPtr, *yPtr; int dir(98), ht = 0, index; ptr = root; if (!root) ( root = createNode(data); return; ) stack(ht) = root; dir(ht++) = 0; while (ptr != NULL) ( if (ptr->data == data) ( printf("Duplicates Not Allowed!!"); return; ) index = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; ptr = ptr->link(index); dir(ht++) = index; ) stack(ht - 1)->link(index) = newnode = createNode(data); while ((ht>= 3) && (stack(ht - 1)->color == RED)) ( if (dir(ht - 2) == 0) ( yPtr = stack(ht - 2)->link(1); if (yPtr != NULL && yPtr->color == RED) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 0) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(1); xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; stack(ht - 2)->link(0) = yPtr; ) xPtr = stack(ht - 2); xPtr->color = RED; yPtr->color = BLACK; xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) else ( yPtr = stack(ht - 2)->link(0); if ((yPtr != NULL) && (yPtr->color == RED)) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 1) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; stack(ht - 2)->link(1) = yPtr; ) xPtr = stack(ht - 2); yPtr->color = BLACK; xPtr->color = RED; xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) ) root->color = BLACK; ) // Delete a node void deletion(int data) ( struct rbNode *stack(98), *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir(98), ht = 0, diff, i; enum nodeColor color; if (!root) ( printf("Tree not available"); return; ) ptr = root; while (ptr != NULL) ( if ((data - ptr->data) == 0) break; diff = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; dir(ht++) = diff; ptr = ptr->link(diff); ) if (ptr->link(1) == NULL) ( if ((ptr == root) && (ptr->link(0) == NULL)) ( free(ptr); root = NULL; ) else if (ptr == root) ( root = ptr->link(0); free(ptr); ) else ( stack(ht - 1)->link(dir(ht - 1)) = ptr->link(0); ) ) else ( xPtr = ptr->link(1); if (xPtr->link(0) == NULL) ( xPtr->link(0) = ptr->link(0); color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) ( root = xPtr; ) else ( stack(ht - 1)->link(dir(ht - 1)) = xPtr; ) dir(ht) = 1; stack(ht++) = xPtr; ) else ( i = ht++; while (1) ( dir(ht) = 0; stack(ht++) = xPtr; yPtr = xPtr->link(0); if (!yPtr->link(0)) break; xPtr = yPtr; ) dir(i) = 1; stack(i) = yPtr; if (i> 0) stack(i - 1)->link(dir(i - 1)) = yPtr; yPtr->link(0) = ptr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = ptr->link(1); if (ptr == root) ( root = yPtr; ) color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; ) ) if (ht color == BLACK) ( while (1) ( pPtr = stack(ht - 1)->link(dir(ht - 1)); if (pPtr && pPtr->color == RED) ( pPtr->color = BLACK; break; ) if (ht link(1); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 0; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(1); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(1) || rPtr->link(1)->color == BLACK) ( qPtr = rPtr->link(0); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(0) = qPtr->link(1); qPtr->link(1) = rPtr; rPtr = stack(ht - 1)->link(1) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(1)->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) else ( rPtr = stack(ht - 1)->link(0); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 1; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(0); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(0) || rPtr->link(0)->color == BLACK) ( qPtr = rPtr->link(1); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(1) = qPtr->link(0); qPtr->link(0) = rPtr; rPtr = stack(ht - 1)->link(0) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(0)->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) ht--; ) ) ) // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) ( if (node) ( inorderTraversal(node->link(0)); printf("%d ", node->data); inorderTraversal(node->link(1)); ) return; ) // Driver code int main() ( int ch, data; while (1) ( printf("1. Insertion 2. Deletion"); printf("3. Traverse 4. Exit"); printf("Enter your choice:"); scanf("%d", &ch); switch (ch) ( case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf(""); break; case 4: exit(0); default: printf("Not available"); break; ) printf(""); ) return 0; )
 // Implementing Red-Black Tree in C++ #include using namespace std; struct Node ( int data; Node *parent; Node *left; Node *right; int color; ); typedef Node *NodePtr; class RedBlackTree ( private: NodePtr root; NodePtr TNULL; void initializeNULLNode(NodePtr node, NodePtr parent) ( node->data = 0; node->parent = parent; node->left = nullptr; node->right = nullptr; node->color = 0; ) // Preorder void preOrderHelper(NodePtr node) ( if (node != TNULL) ( cout right); ) ) // Inorder void inOrderHelper(NodePtr node) ( if (node != TNULL) ( inOrderHelper(node->left); cout left); postOrderHelper(node->right); cout left, key); ) return searchTreeHelper(node->right, key); ) // For balancing the tree after deletion void deleteFix(NodePtr x) ( NodePtr s; while (x != root && x->color == 0) ( if (x == x->parent->left) ( s = x->parent->right; if (s->color == 1) ( s->color = 0; x->parent->color = 1; leftRotate(x->parent); s = x->parent->right; ) if (s->left->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->right->color == 0) ( s->left->color = 0; s->color = 1; rightRotate(s); s = x->parent->right; ) s->color = x->parent->color; x->parent->color = 0; s->right->color = 0; leftRotate(x->parent); x = root; ) ) else ( s = x->parent->left; if (s->color == 1) ( s->color = 0; x->parent->color = 1; rightRotate(x->parent); s = x->parent->left; ) if (s->right->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->left->color == 0) ( s->right->color = 0; s->color = 1; leftRotate(s); s = x->parent->left; ) s->color = x->parent->color; x->parent->color = 0; s->left->color = 0; rightRotate(x->parent); x = root; ) ) ) x->color = 0; ) void rbTransplant(NodePtr u, NodePtr v) ( if (u->parent == nullptr) ( root = v; ) else if (u == u->parent->left) ( u->parent->left = v; ) else ( u->parent->right = v; ) v->parent = u->parent; ) void deleteNodeHelper(NodePtr node, int key) ( NodePtr z = TNULL; NodePtr x, y; while (node != TNULL) ( if (node->data == key) ( z = node; ) if (node->data right; ) else ( node = node->left; ) ) if (z == TNULL) ( cout << "Key not found in the tree"  left == TNULL) ( x = z->right; rbTransplant(z, z->right); ) else if (z->right == TNULL) ( x = z->left; rbTransplant(z, z->left); ) else ( y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) ( x->parent = y; ) else ( rbTransplant(y, y->right); y->right = z->right; y->right->parent = y; ) rbTransplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; ) delete z; if (y_original_color == 0) ( deleteFix(x); ) ) // For balancing the tree after insertion void insertFix(NodePtr k) ( NodePtr u; while (k->parent->color == 1) ( if (k->parent == k->parent->parent->right) ( u = k->parent->parent->left; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->left) ( k = k->parent; rightRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; leftRotate(k->parent->parent); ) ) else ( u = k->parent->parent->right; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->right) ( k = k->parent; leftRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; rightRotate(k->parent->parent); ) ) if (k == root) ( break; ) ) root->color = 0; ) void printHelper(NodePtr root, string indent, bool last) ( if (root != TNULL) ( cout << indent; if (last) ( cout << "R----"; indent += " "; ) else ( cout  right, indent, true); ) ) public: RedBlackTree() ( TNULL = new Node; TNULL->color = 0; TNULL->left = nullptr; TNULL->right = nullptr; root = TNULL; ) void preorder() ( preOrderHelper(this->root); ) void inorder() ( inOrderHelper(this->root); ) void postorder() ( postOrderHelper(this->root); ) NodePtr searchTree(int k) ( return searchTreeHelper(this->root, k); ) NodePtr minimum(NodePtr node) ( while (node->left != TNULL) ( node = node->left; ) return node; ) NodePtr maximum(NodePtr node) ( while (node->right != TNULL) ( node = node->right; ) return node; ) NodePtr successor(NodePtr x) ( if (x->right != TNULL) ( return minimum(x->right); ) NodePtr y = x->parent; while (y != TNULL && x == y->right) ( x = y; y = y->parent; ) return y; ) NodePtr predecessor(NodePtr x) ( if (x->left != TNULL) ( return maximum(x->left); ) NodePtr y = x->parent; while (y != TNULL && x == y->left) ( x = y; y = y->parent; ) return y; ) void leftRotate(NodePtr x) ( NodePtr y = x->right; x->right = y->left; if (y->left != TNULL) ( y->left->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->left) ( x->parent->left = y; ) else ( x->parent->right = y; ) y->left = x; x->parent = y; ) void rightRotate(NodePtr x) ( NodePtr y = x->left; x->left = y->right; if (y->right != TNULL) ( y->right->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->right) ( x->parent->right = y; ) else ( x->parent->left = y; ) y->right = x; x->parent = y; ) // Inserting a node void insert(int key) ( NodePtr node = new Node; node->parent = nullptr; node->data = key; node->left = TNULL; node->right = TNULL; node->color = 1; NodePtr y = nullptr; NodePtr x = this->root; while (x != TNULL) ( y = x; if (node->data data) ( x = x->left; ) else ( x = x->right; ) ) node->parent = y; if (y == nullptr) ( root = node; ) else if (node->data data) ( y->left = node; ) else ( y->right = node; ) if (node->parent == nullptr) ( node->color = 0; return; ) if (node->parent->parent == nullptr) ( return; ) insertFix(node); ) NodePtr getRoot() ( return this->root; ) void deleteNode(int data) ( deleteNodeHelper(this->root, data); ) void printTree() ( if (root) ( printHelper(this->root, "", true); ) ) ); int main() ( RedBlackTree bst; bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); cout << endl << "After deleting" << endl; bst.deleteNode(40); bst.printTree(); )

Εφαρμογές κόκκινου-μαύρου δέντρου

  1. Για την εφαρμογή πεπερασμένων χαρτών
  2. Για την εφαρμογή πακέτων Java: java.util.TreeMapκαιjava.util.TreeSet
  3. Για να εφαρμόσετε τυπικές βιβλιοθήκες προτύπων (STL) στο C ++: multiset, map, multimap
  4. Στο Linux Kernel

ενδιαφέροντα άρθρα...