B-tree: remove: Difference between revisions
Jump to navigation
Jump to search
(Created page with "Category:B-Tree == General Information == == Abstract View == == Induction Basis == == Induction Step == == Complexity == == Further Information ==") |
|||
| Line 11: | Line 11: | ||
== Further Information == | == Further Information == | ||
In the above specification, each node with exactly <math>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>M - 1</math> keys until the first node with more than <math>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. | |||
Revision as of 20:59, 29 September 2014
General Information
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.