3 ms·
Re: vs. red-black trees I don't know... he keeps talking about dynamic memory allocation and total memory usage. If he means cache locality, he should just say
by saurik 16y ago
Re: vs. red-black trees
I don't know... he keeps talking about dynamic memory allocation and total memory usage. If he means cache locality, he should just say cache locality.
Regardless, if you care about cache performance and dynamic allocation, as the goal of a red-black tree is to be reasonably balanced, you can just treat it as a complete tree and use standard binary tree packing on it (the same algorithm normally used for heaps; maybe allocate each level separately, as he is also concerned with the cost of reallocation).