Μπορεί να θεωρηθεί ένα λεξικό ως υλοποιημένο μέσω πίνακα κατακερματισμού ή μέσω ενός κόκκινο-μαύρο δέντρου;

Ναι, ένα λεξικό (dictionary) μπορεί να υλοποιηθεί τόσο μέσω ενός πίνακα κατακερματισμού (hash table) όσο και μέσω ενός ισορροπημένου δέντρου, για παράδειγμα, ένα κόκκινο-μαύρο δέντρο.

• Hash table παρέχει πολύ γρήγορη (αποσβεσμένη O(1)) εισαγωγή, αναζήτηση και διαγραφή με κλειδί, αλλά δεν υποστηρίζει ταξινομημένη διέλευση των στοιχείων.

• Κόκκινο-μαύρο δέντρο είναι ένα ισορροπημένο δυαδικό δέντρο αναζήτησης που εγγυάται λειτουργίες σε O(log n) και υποστηρίζει ταξινομημένη διέλευση, χρήσιμο αν χρειάζεται ταξινομημένο λεξικό.

Η επιλογή εξαρτάται από τις απαιτήσεις: αν η ταχύτητα πρόσβασης και η σειρά δεν είναι σημαντικές — hash table; αν χρειάζεται ταξινομημένο λεξικό — δέντρο.