Ako je určovaná časová zložitosť operácie čítania prvku zo štruktúry dát SortedDictionary?

V C# je dátová štruktúra SortedDictionary implementovaná na základe červeno-čierneho stromu, vyváženého binárneho vyhľadávacieho stromu.

Časová zložitosť operácie čítania (vyhľadávanie prvku podľa kľúča) v SortedDictionary je O(log n), kde n je počet prvkov v slovníku.

To je spôsobené tým, že vyhľadávanie prechádza strom, znižujúc počet kontrol na logaritmický čas, na rozdiel od napríklad Dictionary, kde je vyhľadávanie priemerné O(1), ale bez zoradenia kľúčov.