B-tree: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 7: Line 7:
'''Auxiliary data:'''
'''Auxiliary data:'''
## Pointers, <math>p</math>, <math>p'</math>, <math>p_1</math> and <math>p_2</math> of type "pointer to B-tree node".
## Pointers, <math>p</math>, <math>p'</math>, <math>p_1</math> and <math>p_2</math> of type "pointer to B-tree node".
## A Boolean variable '''''found''''', which is '''''false''''', in the beginning and set '''''true'''' once the key <math>K</math> to be removed is seen.
## A Boolean variable '''''found''''', which is '''''false''''', in the beginning and set '''''true''''' once the key <math>K</math> to be removed is seen.


== Abstract View ==
== Abstract View ==

Revision as of 21:02, 29 September 2014

General Information

Algorithmic problem: Sorted sequence: remove

Type of algorithm: loop

Auxiliary data:

    1. Pointers, [math]\displaystyle{ p }[/math], [math]\displaystyle{ p' }[/math], [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] of type "pointer to B-tree node".
    2. A Boolean variable found, which is false, in the beginning and set true once the key [math]\displaystyle{ K }[/math] to be removed is seen.

Abstract View

Induction Basis

Induction Step

Complexity

Further Information

In the above specification, each node with exactly [math]\displaystyle{ M - 1 }[/math] keys is modified when visited. This is done for precautionary reasons only. With a slight modification, this can be avoided: when the leaf is reached, go back along the traversed path and modify each nodes with [math]\displaystyle{ M - 1 }[/math] keys until the first node with more than [math]\displaystyle{ M - 1 }[/math] keys is visited. Evidently, this reduces the number of modifications. However, chances are high that these nodes have to be modified sooner or later, so the true benefit is not clear. The version of the removal procedure presented here has primarily been selected because its loop invariant is simpler and more intuitive.