Class TestSiblingRedistribution

python/tests/test_bplus_tree.py:559–775

Test sibling key redistribution during deletion

class TestSiblingRedistribution:
    """Test sibling key redistribution during deletion"""

    def test_leaf_can_donate(self):
        """Test that leaf nodes correctly detect when they can donate keys"""
        leaf = LeafNode(capacity=4)  # min_keys = (4-1)//2 = 1

        # Empty leaf cannot donate
        assert not leaf.can_donate()

        # Leaf with 1 key (minimum) cannot donate
        leaf.keys = [1]
        leaf.values = ["one"]
        assert not leaf.can_donate()

        # Leaf with 2 keys can donate
        leaf.keys = [1, 2]
        leaf.values = ["one", "two"]
        assert leaf.can_donate()

        # Leaf with 3 keys can donate
        leaf.keys = [1, 2, 3]
        leaf.values = ["one", "two", "three"]
        assert leaf.can_donate()

    def test_branch_can_donate(self):
        """Test that branch nodes correctly detect when they can donate keys"""
        branch = BranchNode(capacity=4)  # min_keys = (4-1)//2 = 1

        # Empty branch cannot donate
        assert not branch.can_donate()

        # Branch with 1 key (minimum) cannot donate
        branch.keys = [5]
        branch.children = [LeafNode(4), LeafNode(4)]
        assert not branch.can_donate()

        # Branch with 2 keys can donate
        branch.keys = [5, 10]
        branch.children = [LeafNode(4), LeafNode(4), LeafNode(4)]
        assert branch.can_donate()

        # Branch with 3 keys can donate
        branch.keys = [5, 10, 15]
        branch.children = [LeafNode(4), LeafNode(4), LeafNode(4), LeafNode(4)]
        assert branch.can_donate()

    def test_leaf_borrow_from_left(self):
        """Test leaf borrowing keys from left sibling"""
        left = LeafNode(capacity=4)
        right = LeafNode(capacity=4)

        # Set up left sibling with excess keys
        left.keys = [1, 2, 3]
        left.values = ["one", "two", "three"]

        # Set up right sibling with too few keys
        right.keys = [5]