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

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(8 intermediate revisions by 3 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]]
== General Information ==
== General Information ==
'''Algorithmic problem:''' [[See B-tree]]
'''Algorithmic problem:''' [[B-Trees|See B-Trees]]


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


'''Auxiliary data:'''  
'''Auxiliary data:'''


== Abstract View ==
== Abstract View ==
Line 19: Line 21:
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math> are rearranged accordingly.


'''Vairant:''' <math>i</math> increases by <math>1</math>
'''Vairant:''' <math>i</math> increases by <math>1</math>
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: ===
'''Abstract view:'''
 
=== Implementation: ===
 
=== Proof: ===
 
 
== Induction Step ==
=== Abstract view: ===
# Move the next key and children pointer.
# Move the next key and children pointer.
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.


'''Implementation:'''
=== Implementation: ===
# If <math>shiftRight</math>:
# If <math>shiftRight</math>:
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n_-i_+1]</math>
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1]</math>
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]._n-i+1]</math>
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1]</math>
## If <math> i=n+1</math>:
## If <math> i=n+1</math>:
### Set <math>p.children[k].keys[1]:= p.keys[k]
### Set <math>p.children[k].keys[1]:= p.keys[k]</math>
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n]
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] </math>
### Increment <math>p.children[k]_n by one
### Increment <math>p.children[k]_n by one </math>
### Decrement <math>p.children[j-1]_n by one</math>
### Decrement <math>p.children[j-1]_n by one</math>
# Otherwise:
# Otherwise:
Line 52: Line 62:
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one


'''Correctness:'''
=== Correctness: ===
# For the rearrangement of the children pointers, compare the induction basis.
# For the rearrangement of the children pointers, compare the induction basis.
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.


== Complexity ==
== Complexity ==
'''Statement:''' Linear in <math>M</math> in the best and worst case (and hence constant for fixed <math>M</math>).
'''Proof:''' Obvious.

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 [math]\displaystyle{ i \ge 0 }[/math] iterations:

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

Vairant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math]

Break condition: [math]\displaystyle{ (shiftRight }[/math][math]\displaystyle{ i=p.children[k].n+1) }[/math][math]\displaystyle{ ( }[/math]¬[math]\displaystyle{ shiftRight }[/math][math]\displaystyle{ i=p.children[k].n) }[/math]

Before and after each iteration, [math]\displaystyle{ p }[/math] points to a node [math]\displaystyle{ N }[/math] such that the following holds:

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

Variant: The height level of the node to which [math]\displaystyle{ p }[/math] points is decreased by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ p.N \lt 2M }[/math] or (that is, inclusive-or) [math]\displaystyle{ p }[/math] points to the root.

Induction Basis

Abstract view:

Implementation:

Proof:

Induction Step

Abstract view:

  1. Move the next key and children pointer.
  2. If [math]\displaystyle{ shiftRight }[/math] and the break condition applies, the shift is to be done.

Implementation:

  1. If [math]\displaystyle{ shiftRight }[/math]:
    1. If [math]\displaystyle{ i \le n }[/math], set [math]\displaystyle{ p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1] }[/math]
    2. Set [math]\displaystyle{ p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1] }[/math]
    3. If [math]\displaystyle{ i=n+1 }[/math]:
      1. Set [math]\displaystyle{ p.children[k].keys[1]:= p.keys[k] }[/math]
      2. Set [math]\displaystyle{ p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] }[/math]
      3. Increment [math]\displaystyle{ p.children[k]_n by one }[/math]
      4. Decrement [math]\displaystyle{ p.children[j-1]_n by one }[/math]
  2. Otherwise:
    1. If [math]\displaystyle{ i\lt p.children[k]_n }[/math] set [math]\displaystyle{ p.children[k].keys[i]:= p.children[k].keys[i+1] }[/math]
    2. Set [math]\displaystyle{ p.children[k].children[i-1]:= p.children[k].children[i] }[/math]
    3. If [math]\displaystyle{ i=p.children[k]_n, }[/math]decrement [math]\displaystyle{ p.children[k]_n }[/math] by one

Correctness:

  1. For the rearrangement of the children pointers, compare the induction basis.
  2. Note that the increments and decrements of [math]\displaystyle{ p.children[k-1]_n }[/math] and [math]\displaystyle{ p.children[k]_n }[/math] are distributed over induction basis and induction step, but are correct in summary.

Complexity

Statement: Linear in [math]\displaystyle{ M }[/math] in the best and worst case (and hence constant for fixed [math]\displaystyle{ M }[/math]). Proof: Obvious.