B-tree: maximum

From Algowiki
Jump to: navigation, search

General Information

Algorithmic Problem:

Type of algorithm: loop

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

Abstract View

Invariant: Before and after each iteration:

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

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

Break condition:

  1. [math]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]c_n(x)[/math] is the rightest child of a node [math]x[/math].

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