&gt; I wouldn&#x27;t be surprised if the method in the article is faster<p>If that is true, then I suspect we can toss RB trees out of the window. When searching for a key inside a sorted collection, you could use binary search of complexity O(log N), which is the same complexity as searching in an RB tree. So if incremental sorting is faster than updating an RB tree, we wouldn&#x27;t really need RB trees.<p>Of course there could be special circumstances that change this (for example large batches of inserts).