3 ms·
How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but
by larshagencpp 11y ago
How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but maybe you mean something different.
- Scea91 11y agoThe items are sorted after each insertion.
- larshagencpp 11y agoYes, but the incrmental sorting problem requires that the k elements are not only sorted, but are the k first elements of the whole sequence of length N.
- cyphar 11y agoWhy does that make a difference? Every insertion into an RB tree self-balances and sorts the elements. So if you sort the first k elements (insert them in the tree), sorting the next element is fairly cheap (log k). Maybe I'm misunderstanding what you mean.