B-tree: shift key to sibling: Difference between revisions

From Algowiki
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 step ==
=== 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 i0 iterations:

  1. If shiftRight
    1. For j{p.children[k].ni+1,,p.children[k].n{, if j>0, the original values of p.children[k].key[j] are now the values of p.children[k].key[j+1].
    2. For j{p.children[k].ni+1,,p.children[k].n}, the original values of p.children[k].children[j] are now the values of p.children[k].children[j+1].
  2. Otherwise:
    1. For j{2,,i+1}, id jn, the original values of p.children[k].key[j] are now the values of p.children[k].key[j1].
    2. For j{1,,i}, the values of p.children[k].children[j] are now the values of p.children[k].children[j1].
    3. A few moves have already been done (in the preprocessing, in fact):
      1. The former value of p.keys[k] is now the node p.children[k1].
      2. The former value of p.children[k].keys[1] is now at p.keys[k].
      3. The children pointers of p.children[k1] and p.children[k] are rearranged accordingly.

Vairant: i increases by 1

Break condition: (shiftRighti=p.children[k].n+1)(¬shiftRighti=p.children[k].n)

Before and after each iteration, p points to a node N such that the following holds:

  1. In the case p.n<2M, all implementation invariants of B-trees are maintained if the following K can be inserted at some position in N such that after insertion.
  2. In the case p.n=2M, imagine that we could extend p.keys by one more slot (and, consequently, extend .successors by one more slot). Then K can be inserted in N at a position such that - except for the statement about the size of N - all implementation invariants of B-trees are again maintained after insertion.

Variant: The height level of the node to which p points is decreased by 1.

Break condition: p.N<2M or (that is, inclusive-or) p points to the root.

Induction Basis

Abstract view:

Implementation:

Proof:

Induction Step

Abstract view:

  1. Move the next key and children pointer.
  2. If shiftRight and the break condition applies, the shift is to be done.

Implementation:

  1. If shiftRight:
    1. If in, set p.children[k]keys[p.children[k].ni+2]:=p.children[k],keys[p.children[k].ni+1]
    2. Set p.children[k].children[p.children[k].ni+2]:=p.children[k].children[p.children[k]ni+1]
    3. If i=n+1:
      1. Set p.children[k].keys[1]:=p.keys[k]
      2. Set p.keys[k]:=p.children[k1].keys[p.children[k1]n]
      3. Increment p.children[k]nbyone
      4. Decrement p.children[j1]nbyone
  2. Otherwise:
    1. If i<p.children[k]n set p.children[k].keys[i]:=p.children[k].keys[i+1]
    2. Set p.children[k].children[i1]:=p.children[k].children[i]
    3. If i=p.children[k]n,decrement p.children[k]n by one

Correctness:

  1. For the rearrangement of the children pointers, compare the induction basis.
  2. Note that the increments and decrements of p.children[k1]n and p.children[k]n are distributed over induction basis and induction step, but are correct in summary.

Complexity

Statement: Linear in M in the best and worst case (and hence constant for fixed M). Proof: Obvious.