Ποια είναι η χρονική πολυπλοκότητα της ενέργειας διαγραφής ενός στοιχείου από τον συσχετιστικό δοχείο map;

Στην τυπική υλοποίηση ενός συσχετιστικού δοχείου map (για παράδειγμα, στο C++ STL), χρησιμοποιείται ένα ισορροπημένο δέντρο (συνήθως ένα κόκκινο-μαύρο δέντρο). Η χρονική πολυπλοκότητα της διαγραφής ενός στοιχείου από τέτοιο map είναι O(log n), όπου n είναι ο αριθμός των στοιχείων στο δοχείο.

Αυτό οφείλεται στο ότι για να διαγράψετε, πρώτα πρέπει να βρείτε το στοιχείο (χρόνος λογαριθμικός), και στη συνέχεια να αναδιαμορφώσετε το δέντρο, κάτι που επίσης συμβαίνει σε λογαριθμικό χρόνο.