B-tree: merge two siblings

General Information

Algorithmic problem: See B-Trees

Prerequisites:

1. A node $p$ with a key at position $k$ that is not void
2. The number of keys in $p.children[k-1]=p.children[k]=M-1$

Type of algorithm: loop

Auxiliary data:

1. Three pointers $p,p_1,p_2$ of type "pointer to B-tree node".

Abstract View

Invariant: After $i\ge 0$ iterations:

1. $p_1$ points to the left children of the key of $p$ at position $k$ and $p_2$ points to the right children of the key of $p$ at position $k$.
2. $p_1.n=M+i$.
3. $i$ shows on the index of the copied key in $p_2$.

Variant: $i$ increases by $1$.

Break condition: $i=M-1$

Induction Basis

Abstract view:

1. Assign $p_1$ the left children of $p$ at position $k$ and $p_2$ the right children of $p$ at position $k$.
2. Move the key from $p$ at position $k$ to $p_1$ at position $M$.
3. Copy the left children of $p_2$ to the new key in $p1$ at position $M$
4. Change the number of keys in $p_1$ and $p$.

Implementation:

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

Proof:

In the induction basic $p_1$ and $p_2$ are assigned to the left and the right children of the key of $p$ at position $k$ (Invariant 1). The key of $p$ at position $k$ is shifted to $p_1$ at position $M$. So the elements $1\dots ,M$ are filled (B-Tree #5). The number of elements in $p_1$ is increased by one and $p$ is decreased by one (B-Tree #3). So are in $p_{1}M$ keys (Invariant 2). We removed a key of $p$, but because of the invariant of remove ($minM$ keys in $$), now we have $minM-1$ keys in $p$ (B-Tree #4). We added the key from $p$ 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 ($p_1$ and $p_2$ are both children of $p$), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from $p_2$ (Invariant 3).

Induction Step

Abstract view:

1. If not all keys (and children) of $p_2$ are copied, copy the key and children from position $i$ of $p_2$ to position $M+i$ of $p_1$.
2. Otherwise, terminate the algorithm.

Implementation:

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

Correctness:

In the induction step we copy a key and a children from $p_2$ to $p_1$. 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 $p_1.n$ by one for each copied element (B-Tree #3).

Complexity

Statement: Linear in $M-1$ steps in the best and worst case

Proof: Obvious.