Class LeafNode

python/bplustree/bplus_tree.py:669–818

Leaf node containing key-value pairs. Leaf nodes are where all actual key-value pairs are stored in a B+ tree. They are linked together to form a doubly-linked list for efficient range queries. Attributes: capacity: Maximum number of keys this node can hold. keys: Sorte

class LeafNode(Node):
    """Leaf node containing key-value pairs.

    Leaf nodes are where all actual key-value pairs are stored in a B+ tree.
    They are linked together to form a doubly-linked list for efficient range queries.

    Attributes:
        capacity: Maximum number of keys this node can hold.
        keys: Sorted list of keys.
        values: List of values corresponding to keys.
        next: Pointer to the next leaf node (for range queries).
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.keys: List[Any] = []
        self.values: List[Any] = []
        self.next: Optional["LeafNode"] = None  # Link to next leaf

    def is_leaf(self) -> bool:
        return True

    def is_full(self) -> bool:
        return len(self.keys) >= self.capacity

    def __len__(self) -> int:
        return len(self.keys)

    def is_underfull(self) -> bool:
        """Check if leaf has fewer than minimum required keys."""
        min_keys = (self.capacity - 1) // 2
        return len(self.keys) < min_keys

    def can_donate(self) -> bool:
        """Check if leaf can give a key to a sibling (has more than minimum)."""
        min_keys = (self.capacity - 1) // 2
        return len(self.keys) > min_keys

    def borrow_from_left(self, left_sibling: "LeafNode") -> None:
        """Borrow the rightmost key-value from left sibling"""
        if not left_sibling.can_donate():
            raise ValueError("Left sibling cannot donate")

        key = left_sibling.keys.pop()
        value = left_sibling.values.pop()
        self.keys.insert(0, key)
        self.values.insert(0, value)

    def borrow_from_right(self, right_sibling: "LeafNode") -> None:
        """Borrow the leftmost key-value from right sibling"""
        if not right_sibling.can_donate():
            raise ValueError("Right sibling cannot donate")

        key = right_sibling.keys.pop(0)
        value = right_sibling.values.pop(0)
        self.keys.append(key)
        self.values.append(value)