im-rs
im-rs copied to clipboard
Fix a bug in BTree get_next and get_prev search
Closes #215
Previously, we weren't accounting for separator keys correctly in the recursive search. This commit fixes that and adds property tests.
For example, if the root node had a separator with key 66 and the right child node had keys [68, 69, 70, ...], a call to lookup_prev(67) would recurse into the child, find that there is nothing less than or equal to 67, and then bubble up a None value all the way. The correct behavior is to return 66 from the parent node.
The changeset here amends the search to return the previous separator when searching a child returns None.