complexity of set::insert

问题:

I have read that insert operation in a set takes only log(n) time. How is that possible?

To insert, first we have find the location in the sorted array where the new element must sit. Using binary search it takes log(n). Then to insert in that location, all the elements succeeding it should be shifted one place to the right. It takes another n time.

My doubt is based on my understanding that set is implemented as an array and elements are stored in sorted order. Please correct me if my understanding is wrong.

回答1:

std::set is commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity, as the tree is kept balanced.