3 ms·
It looks like the AVL tree implementations do the lazy coding way of updating balance factors and recursively descend to recompute the heights of the left and r
by lamontcg 4y ago
It looks like the AVL tree implementations do the lazy coding way of updating balance factors and recursively descend to recompute the heights of the left and right nodes constantly. The balance factor can be updated directly from the kind of rebalancing rotation being used. I would not call that properly implemented since it is wasting a lot of cycles on that.
- samsquire 4y agoDon't you need to know the balance factor before you know which rotation to do?
- lamontcg 4y agoOnce 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)
- samsquire 4y agoThis 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.