Кадом алгоритм барои муайян кардани ҷойгиршавии унсур дар структураи TreeMap истифода мешавад ва вақти он чӣ қадар аст?

Дар Java, TreeMap дар асоси дарахти сурх-сиёҳ амалӣ шудааст, ки як дарахти ҷустуҷӯи дугонаи мувозинатёфта мебошад. Барои муайян кардани ҷойгиршавии унсур (масалан, ҳангоми илова кардан ё ҷустуҷӯ), аз ҷустуҷӯи дугонаи асосӣ дар асоси калидҳо истифода мешавад, ки калидҳоро бо ҳозирини ҳозир дар дарахт муқоиса мекунад.

Масофаи вақтии амалиётҳои ҷустуҷӯ, илова ва тоза дар TreeMap баробар аст бо O(log n), ки дар он n шумораи унсурҳо дар харита мебошад. Ин тавассути мувозинат кардани дарахт ба даст меояд, ки кафолат медиҳад, ки баландии дарахт ба логарифми шумораи унсурҳо нисбат медиҳад.