B-tree: minimum: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Beschreibung hinzugefügt)
 
(3 intermediate revisions by 3 users not shown)
Line 8: Line 8:


== Abstract View ==
== Abstract View ==
'''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.
'''Break condition:'''
# '''''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.


== Pseudocode ==
== Pseudocode ==
Line 13: Line 23:
  Minimum(''x'')
  Minimum(''x'')
  1 '''while''' leaf(''x'') = false
  1 '''while''' leaf(''x'') = false
  2        ''x'' = c_1(''x'')
  2        ''x'' = c_0(''x'')
  3 '''return''' key_1(''x'')
  3 '''return''' key_0(''x'')
</code>
</code>

Latest revision as of 11:22, 13 October 2014

General Information

Algorithmic Problem:

Type of algorithm: loop

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

Abstract View

Invariant: Before and after each iteration:

  1. 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.

Break condition:

  1. 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.

Pseudocode

Minimum(x)
1 while leaf(x) = false
2        x = c_0(x)
3 return key_0(x)