როგორ განისაზღვრება SortedDictionary მონაცემთა სტრუქტურიდან ელემენტის წაკითხვის ოპერაციის დროითი სირთულე?

C# დარეგისტრირებული მონაცემთა სტრუქტურა SortedDictionary რეალიზებულია წითელი-შავი ხის საფუძველზე — ბალანსირებული ბინარული ძიების ხე.

SortedDictionary-ში წაკითხვის ოპერაციის (ელემენტის ძიება გასაღებით) დროის სირთულე არის O(log n), სადაც n არის ლექსიკონის ელემენტების რაოდენობა.

ეს დაკავშირებულია იმასთან, რომ ძიება გადის ხეზე და ამცირებს შემოწმებების რაოდენობას ლოგარითმული დროით, განსხვავებით, მაგალითად, Dictionary-სგან, სადაც ძიება საშუალოდ არის O(1), მაგრამ გასაღებების სორტირების გარეშე.