I would like to suggest a correction for the AVL trees in chapter 7.
The procedure "ReplaceRightMost" updates the pointer to "repl" in the node
that is just going to be deleted. I checked your Web site and tried your
update, but this update also has a glitch.
Your new approach is to pass "Parent.LeftChild" to "RebalanceRightShrunk".
However, this is only correct when you are in the first recursion level in
"ReplaceRightMost".
It might also be "Parent.RightChild" that you must pass.
Principally, we have to pass that child pointer of "Parent" that points to
"repl".
So, my quick fix, based on your update, was to modify the code to this:
if (shrunk) then
if Parent.LeftChild = repl then
RebalanceRightShrunk(Parent.LeftChild, shrunk)
else
RebalanceRightShrunk(Parent.RightChild, shrunk); |
This seems to work. I tested it with hundred thousends of records I added
and removed.
