# B-tree: merge two siblings

(Redirected from B-Tree:merge two Siblings)

## General Information

Algorithmic problem: See B-Trees

Prerequisites:

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

Type of algorithm: loop

Auxiliary data:

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

## Abstract View

Invariant: After $\displaystyle{ i \ge 0 }$ iterations:

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

Variant: $\displaystyle{ i }$ increases by $\displaystyle{ 1 }$.

Break condition: $\displaystyle{ i=M-1 }$

## Induction Basis

### Abstract view:

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

### Implementation:

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

### Proof:

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

## Induction Step

### Abstract view:

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

### Implementation:

1. if $\displaystyle{ i \le M-1 }$ (that is, not all keys of $\displaystyle{ p_2 }$ are copied):
1. $\displaystyle{ p_1.keys[M+i] := p_2.keys[i]. }$
2. $\displaystyle{ p_1.children[M+i] := p_2.children[i]. }$
3. $\displaystyle{ 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 $\displaystyle{ p_2 }$ to $\displaystyle{ 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 $\displaystyle{ p_1.n }$ by one for each copied element (B-Tree #3).

## Complexity

Statement: Linear in $\displaystyle{ M-1 }$ steps in the best and worst case

Proof: Obvious.