Type of algorithm: loop
Auxiliary data: A pointer p of type "pointer to a B-tree node".
Invariant: Before and after each iteration:
- p points to some node N of the B-tree.
Variant: p is redirected from the current node N to the first child of the current node.
- p points to a leaf of the B-tree.
Description of the algorithm
To get the minimum of a B-Tree, you have to go to the leftest child while it exists.
Minimum(x) 1 while leaf(x) = false 2 x = c_0(x) 3 return key_0(x)