B-tree: shift key to sibling: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
(2 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Videos]] | |||
{{#ev:youtube|https://www.youtube.com/watch?v=vbRZ8h6ROYc|500|right||frame}} | |||
[[Category:B-Tree]] | [[Category:B-Tree]] | ||
[[Category:Algorithm]] | [[Category:Algorithm]] | ||
Line 32: | Line 34: | ||
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root. | '''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root. | ||
== Induction Basis == | |||
== Induction | === Abstract view: === | ||
=== Implementation: === | |||
=== Proof: === | |||
== Induction Step == | |||
=== Abstract view: === | === Abstract view: === | ||
# Move the next key and children pointer. | # Move the next key and children pointer. |
Latest revision as of 23:17, 19 June 2015
General Information
Algorithmic problem: See B-Trees
Type of algorithm: loop
Auxiliary data:
Abstract View
Invariant: After
- If
- For
, if , the original values of are now the values of . - For
, the original values of are now the values of .
- For
- Otherwise:
- For
, id , the original values of are now the values of . - For
, the values of are now the values of . - A few moves have already been done (in the preprocessing, in fact):
- The former value of
is now the node . - The former value of
is now at . - The children pointers of
and are rearranged accordingly.
- The former value of
- For
Vairant:
Break condition:
Before and after each iteration,
- In the case
, all implementation invariants of B-trees are maintained if the following can be inserted at some position in such that after insertion. - In the case
, imagine that we could extend .keys by one more slot (and, consequently, extend .successors by one more slot). Then can be inserted in at a position such that - except for the statement about the size of - all implementation invariants of B-trees are again maintained after insertion.
Variant: The height level of the node to which
Break condition:
Induction Basis
Abstract view:
Implementation:
Proof:
Induction Step
Abstract view:
- Move the next key and children pointer.
- If
and the break condition applies, the shift is to be done.
Implementation:
- If
:- If
, set - Set
- If
:- Set
- Set
- Increment
- Decrement
- Set
- If
- Otherwise:
- If
set - Set
- If
decrement by one
- If
Correctness:
- For the rearrangement of the children pointers, compare the induction basis.
- Note that the increments and decrements of
and are distributed over induction basis and induction step, but are correct in summary.
Complexity
Statement: Linear in