Parts of the tree were getting pruned during removal, the cause is something like:
remove a value that was stored in a leaf node. This would make the node's value nil, but not remove the node.
adding some values would/could create children of this nil-value node. So you had have a nil-value node in the middle of the tree.
when removing a value in a parent of the original node the removeNode code would recurse down, find this nil-value node and remove it, along with everything under it.
The main bug is that when adding nodes in 2, existing nil-value nodes were not reused. Also I'm unsure about the the previous removeNode code working properly.
The code assumes nil-value nodes are only in leafs. So on add we reuse nil-value nodes instead of jumping over them (reuse leaf nil-value nodes). On remove, we "pull-up" values to fill in the nil-value node caused by the removal that is in the middle of the tree.
This PR fixes issues brought up by @hades32 in https://github.com/paulmach/orb/pull/90
Parts of the tree were getting pruned during removal, the cause is something like:
removeNodecode would recurse down, find this nil-value node and remove it, along with everything under it.The main bug is that when adding nodes in 2, existing nil-value nodes were not reused. Also I'm unsure about the the previous removeNode code working properly.
The code assumes nil-value nodes are only in leafs. So on add we reuse nil-value nodes instead of jumping over them (reuse leaf nil-value nodes). On remove, we "pull-up" values to fill in the nil-value node caused by the removal that is in the middle of the tree.