3 ms·

This is very cool! One thing I would be interested in: is there some guarantee that the algorithms are properly implemented? Have you thought about doing some

This is very cool! One thing I would be interested in: is there some guarantee that the algorithms are properly implemented? Have you thought about doing some kind of CI/CD to test that each new version responds with the same results as all the others?

tomrod 4y ago
NIST actually provides a lot of things like this -- what _should_ your method provide as an output -- it's pretty cool to dig through! Example: https://www.nist.gov/itl/sed/products-services/statistical-reference-data-sets-strd https://www.nist.gov/itl/sed/products-services/statistical-r...
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 ago
  Don't you need to know the balance factor before you know which rotation to do?
  - lamontcg 4y ago
    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)
    - samsquire 4y ago
      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.

tomrod 4y ago

NIST actually provides a lot of things like this -- what _should_ your method provide as an output -- it's pretty cool to dig through! Example: https://www.nist.gov/itl/sed/products-services/statistical-reference-data-sets-strd https://www.nist.gov/itl/sed/products-services/statistical-r...

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 ago
Don't you need to know the balance factor before you know which rotation to do?
- lamontcg 4y ago
  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)
  - samsquire 4y ago
    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.