Kāda ir ievietošanas (put) algoritma sarežģītība TreeMap?

Java valodā TreeMap klase ir īstenota uz sarkano-melna koka, līdzsvarota bināro meklēšanas koka.

TreeMap operācijas pievienošanas (put) sarežģītība ir O(log n), kur n ir elementu skaits kartē.

Tas ir tāpēc, ka, lai pievienotu, ir jāatrod jauna atslēgas pozīcija (koka meklēšana) — O(log n).

• Jāievieto elements un, ja nepieciešams, jāsabalansē koks (griezieni un pārkrāsošana) — arī O(log n) sliktākajā gadījumā.

Tādēļ pievienošana TreeMap ir efektīva un mērogojama, pateicoties tās līdzsvarotajai datu struktūrai.