Test that merging can cascade up the tree
(self)
| 850 | assert tree[key] == f"value_{key}" |
| 851 | |
| 852 | def test_cascade_merging(self): |
| 853 | """Test that merging can cascade up the tree""" |
| 854 | tree = BPlusTreeMap(capacity=5) |
| 855 | |
| 856 | # Create a deeper tree structure |
| 857 | for i in range(1, 16): |
| 858 | tree[i] = f"value_{i}" |
| 859 | |
| 860 | # Verify initial state |
| 861 | assert check_invariants(tree) |
| 862 | initial_structure = tree.leaf_count() |
| 863 | |
| 864 | # Delete some keys to potentially cause cascading merges |
| 865 | keys_to_delete = list(range(1, 6)) # Delete fewer keys to avoid edge case |
| 866 | for key in keys_to_delete: |
| 867 | del tree[key] |
| 868 | # Tree should remain valid after each deletion |
| 869 | assert check_invariants(tree) |
| 870 | |
| 871 | # Verify remaining keys |
| 872 | remaining_keys = list(range(6, 16)) |
| 873 | for key in remaining_keys: |
| 874 | assert tree[key] == f"value_{key}" |
| 875 | |
| 876 | # Tree structure may have changed significantly |
| 877 | final_structure = tree.leaf_count() |
| 878 | assert final_structure <= initial_structure |
| 879 | |
| 880 | def test_merge_vs_redistribute_preference(self): |
| 881 | """Test that redistribution is preferred over merging when possible""" |
nothing calls this directly
no test coverage detected