Private class for validating B+ tree invariants. This class encapsulates all the complex logic for checking that a B+ tree maintains its structural properties and ordering constraints.
| 22 | |
| 23 | |
| 24 | class BPlusTreeInvariantChecker: |
| 25 | """ |
| 26 | Private class for validating B+ tree invariants. |
| 27 | |
| 28 | This class encapsulates all the complex logic for checking that a B+ tree |
| 29 | maintains its structural properties and ordering constraints. |
| 30 | """ |
| 31 | |
| 32 | def __init__(self, capacity: int): |
| 33 | self.capacity = capacity |
| 34 | |
| 35 | def check_invariants( |
| 36 | self, root: "Node", leaves: Optional["LeafNode"] = None |
| 37 | ) -> bool: |
| 38 | """ |
| 39 | Check all B+ tree invariants. |
| 40 | |
| 41 | Args: |
| 42 | root: The root node of the tree |
| 43 | leaves: Optional head of the leaf linked list |
| 44 | |
| 45 | Returns: |
| 46 | True if all invariants are satisfied, False otherwise |
| 47 | """ |
| 48 | try: |
| 49 | if not root: |
| 50 | return True |
| 51 | |
| 52 | # Check structural invariants |
| 53 | if not self._check_keys_ascending(root): |
| 54 | print("Invariant violated: Keys not in ascending order") |
| 55 | return False |
| 56 | |
| 57 | if not self._check_min_occupancy(root, is_root=True): |
| 58 | print("Invariant violated: Minimum occupancy constraint") |
| 59 | return False |
| 60 | |
| 61 | if not self._check_max_occupancy(root): |
| 62 | print("Invariant violated: Maximum occupancy constraint") |
| 63 | return False |
| 64 | |
| 65 | if not self._check_branch_structure(root): |
| 66 | print("Invariant violated: Branch node structure") |
| 67 | return False |
| 68 | |
| 69 | # Check leaf-specific invariants |
| 70 | if not self._check_leaf_consistency(root): |
| 71 | print("Invariant violated: Leaf consistency") |
| 72 | return False |
| 73 | |
| 74 | if leaves and not self._check_leaf_ordering(leaves): |
| 75 | print("Invariant violated: Leaf ordering in linked list") |
| 76 | return False |
| 77 | |
| 78 | # Check depth consistency |
| 79 | if not self._check_uniform_depth(root): |
| 80 | print("Invariant violated: Non-uniform leaf depths") |
| 81 | return False |
no outgoing calls