Πώς αξιολογείται η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου στο TreeSet;

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

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

Παράδειγμα:

TreeSet<Integer> set = new TreeSet<>();
set.add(10); // O(log n)
set.add(5);  // O(log n)
set.add(20); // O(log n)