Class TestNodeUnderflow

python/tests/test_bplus_tree.py:402–509

Test node underflow detection

class TestNodeUnderflow:
    """Test node underflow detection"""

    def test_leaf_underflow_detection(self):
        """Test that leaf nodes correctly detect underflow"""
        leaf = LeafNode(capacity=4)  # min_keys = (4-1)//2 = 1

        # Empty leaf is underfull
        assert leaf.is_underfull()

        # Single key is at minimum (not underfull)
        leaf.insert(1, "one")
        assert not leaf.is_underfull()

        # Two keys is definitely not underfull
        leaf.insert(2, "two")
        assert not leaf.is_underfull()

        # More keys is definitely not underfull
        leaf.insert(3, "three")
        assert not leaf.is_underfull()

    def test_branch_underflow_detection(self):
        """Test that branch nodes correctly detect underflow"""
        branch = BranchNode(capacity=4)  # min_keys = (4-1)//2 = 1

        # Empty branch is underfull
        assert branch.is_underfull()

        # Single key is at minimum (not underfull)
        branch.keys.append(5)
        assert not branch.is_underfull()

        # Two keys is definitely not underfull
        branch.keys.append(10)
        assert not branch.is_underfull()

        # More keys is definitely not underfull
        branch.keys.append(15)
        assert not branch.is_underfull()

    def test_underflow_after_deletion_creates_violation(self):
        """Test that deleting keys can create underflow violations"""
        tree = BPlusTreeMap(capacity=4)

        # Create a tree with enough items to have branch nodes
        for i in range(1, 10):
            tree[i] = f"value_{i}"

        # Delete many items to potentially create underflow
        # (This test documents current behavior - underflow handling will be added later)
        del tree[1]
        del tree[2]
        del tree[3]
        del tree[4]

        # Check if any nodes are underfull (they might be, which is expected for now)
        has_underflow = self._tree_has_underflow(tree)