Ryan Fogarty <ryan.fogarty.msece <at> gmail.com> writes:
I'm hoping to use multi-index' ordered_index (non-unique) to do a fast running median. Given a set of M numbers and a window size of N compute the medians (for each of M - N + 1 solutions). Here is my solution:
[...]
However, what I was hoping was that I could get the root node directly. ordered_index doesn't expose an iterator to root() so I put it in ordered_index.hpp as:
iterator beginAtRoot(){return make_iterator(root());}
However, this isn't working out because the tree isn't always balanced. My question is 2-fold is there any way to force the internal red-black tree to stay balanced; and secondly, would that have an appreciable performance penalty.
Hi Ryan, Excuse my very late answering, been on vacation the last two weeks. ordered_index internal implementation relies on red-back trees, which are not perfectly balanced but only roughly so (the longest root-to-leaf path is at most twice as long as the shortest one). I don't think it's easy to modify the handling code to improve on that. Joaquín M López Muñoz Telefónica, Invewstigación y Desarrollo