B-tree: maximum

General Information

Algorithmic Problem:

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to a B-tree node".

Abstract View

Invariant: Before and after each iteration:

1. [math]\displaystyle{ p }[/math] points to some node [math]\displaystyle{ N }[/math] of the B-tree.

Variant: [math]\displaystyle{ p }[/math] is redirected from the current node [math]\displaystyle{ p }[/math] to the first child of the current node.

Break condition:

1. [math]\displaystyle{ p }[/math] points to a leaf of the B-tree.

Description of the algorithm

To get the maximum of a B-Tree, you have to go to the rightest child while it exists.

Pseudocode

[math]\displaystyle{ c_n(x) }[/math] is the rightest child of a node [math]\displaystyle{ x }[/math].

Minimum(x)
1 while leaf(x) = false
2        x = c_n(x)
3 return key_n(x)