B-tree: merge two siblings: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "Category:B-Tree Category:Algorithm == General Information == '''Algorithmic problem:''' See B-Tree '''Prerequisites:''' # A node <math>p</math> with a key at positio...")
 
No edit summary
 
(9 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 9: Line 11:


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop
'''Auxiliary data:'''  
'''Auxiliary data:'''  
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".


== Abstract View ==
== Abstract View ==
Line 22: Line 24:


'''Break condition:''' <math>i=M-1</math>
'''Break condition:''' <math>i=M-1</math>
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds:
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.


== Induction Basis ==
== Induction Basis ==
'''Abstract view:'''
=== Abstract view: ===
# <math>p</math> is set to the input pointer.
# 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>.
# <math>p_1</math> and <math>p_2</math> are void initially.
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.
# Copy the left children of <math>p_2</math> to the new key in <math>p1</math> at position <math>M</math>
# Change the number of keys in <math>p_1</math> and <math>p</math>.


'''Implementation:''' Obvious.
=== 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.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.children[M] := p_2.children[0]</math>
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math>


'''Proof:''' The requirement on the input pointer immediately implies the invariants.
=== 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"