Hacker News new | past | comments | ask | show | jobs | submit login

Don't you need to know the balance factor before you know which rotation to do?



Once they're done with the rotation they're recomputing the balance factor by calling something like height(left) and height(right) which recursively descend to count the height on both sides. You don't need to do that. Given the old balance factor and the rotation you can compute the new balance factor.

(Some really bad implementations don't even store the old balance factor in the node and call a recursive height function to figure it out beforehand as well, I just skimmed the implementations I looked at so I didn't check to see if they were doing that as well)


This is something that the compiler could optimize.

If you have all the temporary ingredients of the data, you could work out when height(left) height(right) needs to be evaluated.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: