B-tree: merge two siblings

From Algowiki
Jump to: navigation, search

General Information

Algorithmic problem: See B-Trees

Prerequisites:

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

Type of algorithm: loop

Auxiliary data:

  1. Three pointers [math]p, p_1, p_2 [/math] of type "pointer to B-tree node".

Abstract View

Invariant: After [math] i \ge 0[/math] iterations:

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

Variant: [math]i[/math] increases by [math]1[/math].

Break condition: [math]i=M-1[/math]

Induction Basis

Abstract view:

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

Implementation:

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

Proof:

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

Induction Step

Abstract view:

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

Implementation:

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

Complexity

Statement: Linear in [math]M-1[/math] steps in the best and worst case

Proof: Obvious.