B-tree: merge two siblings

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.