3 ms·

Do you happen to remember what improvements you could get from the new algorithm when it comes to memory usage and execution time? Or was this more about gettin

• EdSchouten 8y ago
  This was already a couple of years ago, so I forgot some of the details. It made a lot of sense in this case to not have a parent pointer in the tree nodes, for the reason that that would bump the size of a node just over 32 bytes (left, right, parent and data pointers, and a balance count). This would cause libc's allocator to allocate 64 bytes per node instead. I also seem to remember that the performance of this implementation was pretty much on par with a conventional recursive implementation. The only differences were that use of stack space was a lot less (i.e., constant) and that the machine code generated by Clang was a tiny bit smaller. I suspect that's because the optimizer didn't have to deal with recursive code.