Junior — Middle
Hogyan értékeljük a TreeSet-hez való elem hozzáadásának időbeli összetettségét?
sobes.tech MI
Válasz az MI-től
Java-ban a TreeSet osztály egy vörös-fekete fára épül, amely egy kiegyensúlyozott bináris keresőfa. A TreeSet-be történő elem hozzáadásának időkomplexitása O(log n), ahol n az elemszám a halmazban.
Ez azért van, mert az elem beszúrásakor először keresés történik a fában, hogy megtalálja a megfelelő helyet, majd a fa kiegyensúlyozása következik, ami logaritmikus időt vesz igénybe.
Példa:
TreeSet<Integer> set = new TreeSet<>();
set.add(10); // O(log n)
set.add(5); // O(log n)
set.add(20); // O(log n)