B-tree: minimum: Difference between revisions
Jump to navigation
Jump to search
(Created page with "Minimum(x) :while leaf(x) = false ::x = c1(x) :return key1(x)") |
(Beschreibung hinzugefügt) |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
Minimum(x) | == 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: | |||
# '''''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 == | |||
<code> | |||
Minimum(''x'') | |||
1 '''while''' leaf(''x'') = false | |||
2 ''x'' = c_0(''x'') | |||
3 '''return''' key_0(''x'') | |||
</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:
- 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
Minimum(x)
1 while leaf(x) = false
2 x = c_0(x)
3 return key_0(x)