Hogyan határozható meg az std::map-ben lévő elem keresésének időbeli összetettsége?

A std::map egy kiegyensúlyozott bináris fát (általában piros-fekete fa) használ, ezért egy elem keresése időbonyolultságú O(log n), ahol n a konténerben lévő elemek száma. Ez abból adódik, hogy a keresés során az elemet összehasonlítják a fa csomópontjaival, és vagy a bal, vagy a jobb alárendelt fába lépnek, így minden lépésben a keresési terület feleződik.