Class TestNodeMerging

python/tests/test_bplus_tree.py:778–903

Test node merging during deletion

class TestNodeMerging:
    """Test node merging during deletion"""

    def test_leaf_merge_with_right(self):
        """Test merging a leaf with its right sibling"""
        left = LeafNode(capacity=4)
        right = LeafNode(capacity=4)

        # Set up left leaf with underfull keys
        left.keys = [1]
        left.values = ["one"]

        # Set up right leaf
        right.keys = [5, 6]
        right.values = ["five", "six"]

        # Set up linked list
        left.next = right

        # Merge left with right
        left.merge_with_right(right)

        # Verify merge results
        assert left.keys == [1, 5, 6]
        assert left.values == ["one", "five", "six"]
        assert left.next == right.next  # Should skip merged node

    def test_branch_merge_with_right(self):
        """Test merging a branch with its right sibling"""
        left = BranchNode(capacity=4)
        right = BranchNode(capacity=4)

        # Set up left branch with underfull keys
        left.keys = [5]
        left.children = [LeafNode(4), LeafNode(4)]

        # Set up right branch
        right.keys = [15, 20]
        right.children = [LeafNode(4), LeafNode(4), LeafNode(4)]

        # Merge with separator key 10
        left.merge_with_right(right, 10)

        # Verify merge results
        assert left.keys == [5, 10, 15, 20]
        assert len(left.children) == 5  # 2 + 3

    def test_merging_during_deletion_creates_balanced_tree(self):
        """Test that merging during deletion maintains tree balance"""
        tree = BPlusTreeMap(capacity=5)  # Small capacity to force merging

        # Insert keys to create a tree structure
        for i in range(1, 10):
            tree[i] = f"value_{i}"

        # Verify initial state
        assert check_invariants(tree)
        initial_leaf_count = tree.leaf_count()