B-tree: merge two siblings

General Information

Algorithmic problem: See B-Tree

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 the node is not full, the key can be inserted, and we are done.
   1. If the new key is larger than all keys stored in the node, it can be appended.
   2. 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.
2. On the other hand, if the node is indeed full, the key cannot be inserted. In this case:
   1. The current node [math]\displaystyle{ N }[/math] will be split into two nodes, [math]\displaystyle{ N_1 }[/math] and [math]\displaystyle{ N_2 }[/math].
   2. [math]\displaystyle{ N_1 }[/math] will contain all keys strictly less than the median of { [math]\displaystyle{ p.keys[1], ... , p.keys[p.n], K' }[/math] }
   3. Analogously, [math]\displaystyle{ N_2 }[/math] will contain all keys strictly greater than the median of { [math]\displaystyle{ p.keys[1], ... , p.keys[p.n], K' }[/math] }.
   4. Next we try to
   5. If [math]\displaystyle{ K' }[/math] is that median itself, nothing is to be done on the current node.
   6. Otherwise, the median of [math]\displaystyle{ \{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]\displaystyle{ K' }[/math] . If the current node is the root, which we next try to insert in the predecessor of

Implementation:

1. If [math]\displaystyle{ p.n = 2M }[/math]
   1. If [math]\displaystyle{ p.keys[M] \lt K' \lt p.keys[M + 1] }[/math], break the iteration and continue the loop.
   2. Otherwise: [math]\displaystyle{ x:= M }[/math] if [math]\displaystyle{ K' \lt p.keys[M] }[/math], and [math]\displaystyle{ x:= M+1 }[/math] otherwise.
   3. Set [math]\displaystyle{ K'' := p.keys[x] }[/math].
   4. For [math]\displaystyle{ j \in \{x+1, \dots, p.n \} }[/math] (in this order), set [math]\displaystyle{ p.keys [j-1]:= p.keys[j] }[/math] and [math]\displaystyle{ p. successor[j-1]:= p.successors[j] }[/math].
2. If [math]\displaystyle{ p.keys[p.n] \lt K' }[/math], insert the new (key, value)-pair at position [math]\displaystyle{ p.keys[p.n+1 }[/math]
3. Otherwise:
   1. Let [math]\displaystyle{ i \in \{ 1, \dots , p.n \} }[/math] be minimal subject to [math]\displaystyle{ K' \lt p.keys[i] }[/math]
   2. For [math]\displaystyle{ j \in \{ p.n, \dots , i \} }[/math] (in this order), set [math]\displaystyle{ p.keys[j+1]:= p.keys[j]. }[/math]
4. If [math]\displaystyle{ p.n \lt 2M }[/math], set [math]\displaystyle{ p.n:= p.n+1 }[/math] and terminate the algorithm.
5. Otherwise, set [math]\displaystyle{ K':= K'' }[/math].

Correctness: Easy to see.