Millist algoritmi kasutatakse TreeMap elemendi otsimiseks ja kui tõhus see on?

Java-s on TreeMap rakendatud punase-musta puu alusel, mis on tasakaalustatud binaarne otsingupuu. Elementi otsitakse puu sees binaarse otsingu algoritmiga, mis tasakaalustamise tõttu hoiab puu kõrgust umbes (O(\log n)).

See tagab tõhusa otsingu, sisestamise ja kustutamise aja (O(\log n)), mis on märkimisväärselt kiirem kui lineaarne otsing mittesorteeritud struktuuris.

TreeMap kasutamise näide:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "kümme");
map.put(5, "viis");
map.put(20, " kakskümmend");

String value = map.get(10); // otsing võtmega 10, aeg - O(log n)