B-tree: merge two siblings: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(6 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:''' See [[B-Trees]]


'''Prerequisites:'''  
'''Prerequisites:'''  
Line 24: Line 26:


== Induction Basis ==
== Induction Basis ==
'''Abstract view:'''
=== Abstract view: ===
# Assign <math>p_1</math> the left children of <math>p</math> at position <math>k</math> and <math>p_2</math> the right children of <math>p</math> at position <math>k</math>.
# Assign <math>p_1</math> the left children of <math>p</math> at position <math>k</math> and <math>p_2</math> the right children of <math>p</math> at position <math>k</math>.
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.
Line 30: Line 32:
# Change the number of keys in <math>p_1</math> and <math>p</math>.
# Change the number of keys in <math>p_1</math> and <math>p</math>.


'''Implementation:'''
=== Implementation: ===
# Set <math>p_1 := p.children[k-1]</math> and <math>p_2 := p.children[k]</math> and <math>p.children[k] := void</math>.
# Set <math>p_1 := p.children[k-1]</math> and <math>p_2 := p.children[k]</math> and <math>p.children[k] := void</math>.
# Set <math>p_1.keys[M] := p.keys[k]</math> and for <math>j \in k+1, \dots , p.n</math> (in this order), set <math>p.keys[j-1] := p.keys[j]</math>  
# Set <math>p_1.keys[M] := p.keys[k]</math> and for <math>j \in k+1, \dots , p.n</math> (in this order), set <math>p.keys[j-1] := p.keys[j]</math>  
Line 36: Line 38:
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math>
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math>


'''Proof:''' In the induction basic <math>p_1</math> and <math>p_2</math> are assigned to the left and the right children of the key of <math>p</math> at position <math>k</math> (Invariant 1). The key of <math>p</math> at position <math>k</math> is shifted to <math>p_1</math> at position <math>M</math>. So the elements <math>1 \dots , M</math> are filled (B-Tree #5). The number of elements in <math>p_1</math> is increased by one and <math>p</math> is decreased by one (B-Tree #3). So are in <math>p_1 M</math> keys (Invariant 2). We removed a key of <math>p</math>, but because of the invariant of remove (<math>minM</math> keys in <math></math>), now we have <math>minM - 1</math> keys in <math>p</math> (B-Tree #4). We added the key from <math>p</math> to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level (<math>p_1</math> and <math>p_2</math> are both children of <math>p</math>), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from <math>p_2</math> (Invariant 3).
=== Proof: ===
In the induction basic <math>p_1</math> and <math>p_2</math> are assigned to the left and the right children of the key of <math>p</math> at position <math>k</math> (Invariant 1). The key of <math>p</math> at position <math>k</math> is shifted to <math>p_1</math> at position <math>M</math>. So the elements <math>1 \dots , M</math> are filled (B-Tree #5). The number of elements in <math>p_1</math> is increased by one and <math>p</math> is decreased by one (B-Tree #3). So are in <math>p_1 M</math> keys (Invariant 2). We removed a key of <math>p</math>, but because of the invariant of remove (<math>minM</math> keys in <math></math>), now we have <math>minM - 1</math> keys in <math>p</math> (B-Tree #4). We added the key from <math>p</math> to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level (<math>p_1</math> and <math>p_2</math> are both children of <math>p</math>), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from <math>p_2</math> (Invariant 3).


== Induction Step ==
== Induction Step ==
'''Abstract view:'''
=== Abstract view: ===
# If the node is not full, the key can be inserted, and we are done.
# If not all keys (and children) of <math>p_2</math> are copied, copy the key and children from position <math>i</math> of <math>p_2</math> to position <math>M+i</math> of <math>p_1</math>.
## If the new key is larger than all keys stored in the node, it can be appended.
# Otherwise, terminate the algorithm.
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.
## <math>N_1</math>  will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.
## Next we try to
## If <math>K'</math> is that median itself, nothing is to be done on the current node.
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math>  is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of


'''Implementation:'''
===Implementation: ===
# If <math>p.n = 2M</math>
# if <math>i \le M-1</math> (that is, not all keys of <math>p_2</math> are copied):
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.
## <math>p_1.keys[M+i] := p_2.keys[i].</math>
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.
## <math>p_1.children[M+i] := p_2.children[i].</math>
## Set <math> K'' := p.keys[x]</math>.
## <math>p_1.n := p_1.n+1</math>
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.
# Otherwise, terminate the algorithm.
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math>
# Otherwise:
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math>
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math>
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.
# Otherwise, set <math>K':= K''</math>.


'''Correctness:''' Easy to see.
=== Correctness: ===
In the induction step we copy a key and a children from <math>p_2</math> to <math>p_1</math>. The copy is in the same order as the elements and on the same level. Implementation invariants #1, #2, #4, #6, #7 and #8 are trivially fulfilled. In step 1.3 we increase <math>p_1.n</math> by one for each copied element (B-Tree #3).


== Complexity ==
== Complexity ==
'''Statement:''' Linear in <math>M-1</math> steps in the best and worst case
'''Proof:''' Obvious.

Latest revision as of 23:19, 19 June 2015

General Information

Algorithmic problem: See B-Trees

Prerequisites:

  1. A node [math]\displaystyle{ p }[/math] with a key at position [math]\displaystyle{ k }[/math] that is not void
  2. The number of keys in [math]\displaystyle{ p.children[k-1]=p.children[k]=M-1 }[/math]

Type of algorithm: loop

Auxiliary data:

  1. Three pointers [math]\displaystyle{ p, p_1, p_2 }[/math] of type "pointer to B-tree node".

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. [math]\displaystyle{ p_1 }[/math] points to the left children of the key of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math] and [math]\displaystyle{ p_2 }[/math] points to the right children of the key of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math].
  2. [math]\displaystyle{ p_1.n = M+i }[/math].
  3. [math]\displaystyle{ i }[/math] shows on the index of the copied key in [math]\displaystyle{ p_2 }[/math].

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

Break condition: [math]\displaystyle{ i=M-1 }[/math]

Induction Basis

Abstract view:

  1. Assign [math]\displaystyle{ p_1 }[/math] the left children of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math] and [math]\displaystyle{ p_2 }[/math] the right children of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math].
  2. Move the key from [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math] to [math]\displaystyle{ p_1 }[/math] at position [math]\displaystyle{ M }[/math].
  3. Copy the left children of [math]\displaystyle{ p_2 }[/math] to the new key in [math]\displaystyle{ p1 }[/math] at position [math]\displaystyle{ M }[/math]
  4. Change the number of keys in [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p }[/math].

Implementation:

  1. Set [math]\displaystyle{ p_1 := p.children[k-1] }[/math] and [math]\displaystyle{ p_2 := p.children[k] }[/math] and [math]\displaystyle{ p.children[k] := void }[/math].
  2. Set [math]\displaystyle{ p_1.keys[M] := p.keys[k] }[/math] and for [math]\displaystyle{ j \in k+1, \dots , p.n }[/math] (in this order), set [math]\displaystyle{ p.keys[j-1] := p.keys[j] }[/math]
  3. Set [math]\displaystyle{ p_1.children[M] := p_2.children[0] }[/math]
  4. Set [math]\displaystyle{ p_1.n := p_1.n+1 }[/math] and set [math]\displaystyle{ p.n := p.n-1 }[/math]

Proof:

In the induction basic [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] are assigned to the left and the right children of the key of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math] (Invariant 1). The key of [math]\displaystyle{ p }[/math] at position [math]\displaystyle{ k }[/math] is shifted to [math]\displaystyle{ p_1 }[/math] at position [math]\displaystyle{ M }[/math]. So the elements [math]\displaystyle{ 1 \dots , M }[/math] are filled (B-Tree #5). The number of elements in [math]\displaystyle{ p_1 }[/math] is increased by one and [math]\displaystyle{ p }[/math] is decreased by one (B-Tree #3). So are in [math]\displaystyle{ p_1 M }[/math] keys (Invariant 2). We removed a key of [math]\displaystyle{ p }[/math], but because of the invariant of remove ([math]\displaystyle{ minM }[/math] keys in [math]\displaystyle{ }[/math]), now we have [math]\displaystyle{ minM - 1 }[/math] keys in [math]\displaystyle{ p }[/math] (B-Tree #4). We added the key from [math]\displaystyle{ p }[/math] to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level ([math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] are both children of [math]\displaystyle{ p }[/math]), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from [math]\displaystyle{ p_2 }[/math] (Invariant 3).

Induction Step

Abstract view:

  1. If not all keys (and children) of [math]\displaystyle{ p_2 }[/math] are copied, copy the key and children from position [math]\displaystyle{ i }[/math] of [math]\displaystyle{ p_2 }[/math] to position [math]\displaystyle{ M+i }[/math] of [math]\displaystyle{ p_1 }[/math].
  2. Otherwise, terminate the algorithm.

Implementation:

  1. if [math]\displaystyle{ i \le M-1 }[/math] (that is, not all keys of [math]\displaystyle{ p_2 }[/math] are copied):
    1. [math]\displaystyle{ p_1.keys[M+i] := p_2.keys[i]. }[/math]
    2. [math]\displaystyle{ p_1.children[M+i] := p_2.children[i]. }[/math]
    3. [math]\displaystyle{ p_1.n := p_1.n+1 }[/math]
  2. Otherwise, terminate the algorithm.

Correctness:

In the induction step we copy a key and a children from [math]\displaystyle{ p_2 }[/math] to [math]\displaystyle{ p_1 }[/math]. The copy is in the same order as the elements and on the same level. Implementation invariants #1, #2, #4, #6, #7 and #8 are trivially fulfilled. In step 1.3 we increase [math]\displaystyle{ p_1.n }[/math] by one for each copied element (B-Tree #3).

Complexity

Statement: Linear in [math]\displaystyle{ M-1 }[/math] steps in the best and worst case

Proof: Obvious.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&oldid=3381"