Jaka jest złożoność algorytmu wstawiania (put) w TreeMap?

W Javie klasa TreeMap jest zaimplementowana na podstawie drzewa czerwono-czarnego, zbalansowanego drzewa binarnego wyszukiwania.

Złożoność operacji wstawiania (put) w TreeMap wynosi O(log n), gdzie n to liczba elementów w mapie.

Dzieje się tak, ponieważ aby wstawić element:

• Należy znaleźć pozycję dla nowego klucza (wyszukiwanie w drzewie) — O(log n).
• Wstawić element i w razie potrzeby zbalansować drzewo (obrót i zmiana koloru) — również O(log n) w najgorszym przypadku.

W związku z tym, wstawianie do TreeMap jest wydajne i skalowalne dzięki zbalansowanej strukturze danych.