# 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$
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.