Internal (branch) node containing keys and child pointers. Branch nodes guide the search through the tree. They contain separator keys and pointers to child nodes. For n keys, there are n+1 children. Attributes: capacity: Maximum number of keys this node can hold. keys:
| 819 | |
| 820 | |
| 821 | class BranchNode(Node): |
| 822 | """Internal (branch) node containing keys and child pointers. |
| 823 | |
| 824 | Branch nodes guide the search through the tree. They contain separator keys |
| 825 | and pointers to child nodes. For n keys, there are n+1 children. |
| 826 | |
| 827 | Attributes: |
| 828 | capacity: Maximum number of keys this node can hold. |
| 829 | keys: Sorted list of separator keys. |
| 830 | children: List of child nodes (leaves or other branches). |
| 831 | |
| 832 | Invariants: |
| 833 | - len(children) == len(keys) + 1 |
| 834 | - All keys in children[i] < keys[i] |
| 835 | - All keys in children[i+1] >= keys[i] |
| 836 | """ |
| 837 | |
| 838 | def __init__(self, capacity: int): |
| 839 | self.capacity = capacity |
| 840 | self.keys: List[Any] = [] |
| 841 | self.children: List[Node] = [] |
| 842 | |
| 843 | def is_leaf(self) -> bool: |
| 844 | return False |
| 845 | |
| 846 | def is_full(self) -> bool: |
| 847 | return len(self.keys) >= self.capacity |
| 848 | |
| 849 | def __len__(self) -> int: |
| 850 | return len(self.keys) |
| 851 | |
| 852 | def is_underfull(self) -> bool: |
| 853 | """Check if branch has fewer than minimum required keys""" |
| 854 | min_keys = (self.capacity - 1) // 2 |
| 855 | return len(self.keys) < min_keys |
| 856 | |
| 857 | def can_donate(self) -> bool: |
| 858 | """Check if branch can give a key to a sibling (has more than minimum)""" |
| 859 | min_keys = (self.capacity - 1) // 2 |
| 860 | return len(self.keys) > min_keys |
| 861 | |
| 862 | def borrow_from_left(self, left_sibling: "BranchNode", separator_key: Any) -> Any: |
| 863 | """Borrow the rightmost key and child from left sibling, returns new separator""" |
| 864 | if not left_sibling.can_donate(): |
| 865 | raise ValueError("Left sibling cannot donate") |
| 866 | |
| 867 | # Take the separator key as our leftmost key |
| 868 | self.keys.insert(0, separator_key) |
| 869 | |
| 870 | # Take the rightmost child from left sibling |
| 871 | child = left_sibling.children.pop() |
| 872 | self.children.insert(0, child) |
| 873 | |
| 874 | # The rightmost key from left sibling becomes the new separator |
| 875 | return left_sibling.keys.pop() |
| 876 | |
| 877 | def borrow_from_right(self, right_sibling: "BranchNode", separator_key: Any) -> Any: |
| 878 | """Borrow the leftmost key and child from right sibling, returns new separator""" |
no outgoing calls