Arc Forumnew | comments | leaders | submitlogin
2 points by pg 6157 days ago | link | parent

Are you sure it works the same? Bst-rem-edge is simpler than bst-rem; it doesn't rebalance the tree.


2 points by rkts 6157 days ago | link

Maybe I'm not understanding your code (it's kind of cryptic...) but it does seem the same to me. When bst-rem removes a node with one child, it just grabs the other child. This is the same thing bst-rem-edge does.

Your 'bubble' function calls bst-edge to find the left/rightmost node and then calls bst-rem-edge to remove it. You could just as well call bst-edge and then bst-rem on the result; either way you traverse the tree twice. I can't imagine a situation where you'd just want bst-rem-edge by itself.

Come to think of it, I don't know why you need bst-edge either. It's simpler to just have min and max functions that return an element, as in the Haskell solution.

-----