Кой алгоритъм се използва за търсене на елемент в TreeMap и колко е ефективен?

TreeMap в Java е реализиран на базата на червено-черен дърво, което е разновидност на балансирано двоично дърво за търсене. За търсене на елемент се използва алгоритъм за двоично търсене в дървото, който благодарение на балансирането поддържа височината на дървото приблизително равна на (O(\log n)).

Това осигурява ефективно търсене, вмъкване и изтриване на елементи за време (O(\log n)), което е значително по-бързо от линейното търсене в несортирана структура.

Пример за използване на TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "десет");
map.put(5, "пет");
map.put(20, "двадесет");

String value = map.get(10); // търсене по ключ 10 в O(log n)