B-tree: remove

General Information

Algorithmic problem: Sorted sequence: remove

Type of algorithm: loop

Auxiliary data:

1. 1. Pointers, [math]\displaystyle{ p }[/math], [math]\displaystyle{ p' }[/math], [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] of type "pointer to B-tree node".
   2. A Boolean variable found, which is false, in the beginning and set true once the key [math]\displaystyle{ K }[/math] to be removed is seen.

Abstract View

Invariant:

1. [math]\displaystyle{ p }[/math] points to a node of the B-tree.
2. If [math]\displaystyle{ found = false }[/math], [math]\displaystyle{ K }[/math] is in the range of the node to which [math]\displaystyle{ p }[/math] points.
3. It is [math]\displaystyle{ found = true }[/math] if, and only if, [math]\displaystyle{ K }[/math] is contained at least once in one of the current nodes of previous iterations.
4. If [math]\displaystyle{ found = true }[/math]
   1. [math]\displaystyle{ p' }[/math] points to a node where [math]\displaystyle{ K }[/math] is currently stored.
   2. The immediate predecessor of [math]\displaystyle{ K }[/math] is in the range of the node to which [math]\displaystyle{ p }[/math] points.
5. If [math]\displaystyle{ p }[/math] points to the root, at least two keys are currently stored in the root; otherwise, at least [math]\displaystyle{ M }[/math] keys are currently stored in the node to which [math]\displaystyle{ p }[/math] points.

Variant: [math]\displaystyle{ p }[/math] is redirected to a node one level deeper.

Break condition: [math]\displaystyle{ p }[/math] points to a leaf.

Remark: For example, the height of the subtree rooted at the node to which [math]\displaystyle{ p }[/math] points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

Induction Basis

Abstract view:

1. If the tree is empty, terminate the algorithm and return false
2. The pointer [math]\displaystyle{ p }[/math] is initialized so as to point to the root [math]\displaystyle{ N }[/math]
3. If [math]\displaystyle{ N }[/math] is a leaf:
   1. Remove [math]\displaystyle{ K }[/math] if contained in [math]\displaystyle{ N }[/math].
   2. If [math]\displaystyle{ N }[/math] is empty now, make the tree empty.
   3. Terminate the algorithm and return true if [math]\displaystyle{ K }[/math] was contained in [math]\displaystyle{ N }[/math], false otherwise.
4. Otherwise, if [math]\displaystyle{ N }[/math] contains exactly one key and is not a leaf: rearrange the root and its two children appropriately.

Implementation:

1. If the tree is empty, terminate the algorithm and return false.
2. Let [math]\displaystyle{ p }[/math] point to the root.
3. If [math]\displaystyle{ p.children[0] = void }[/math] (that is, the root is a leaf):
   1. If [math]\displaystyle{ K }[/math] is contained in the root, say at position [math]\displaystyle{ k }[/math]:
      1. Remove the occurrence of [math]\displaystyle{ K }[/math] at position [math]\displaystyle{ k }[/math].
      2. If the root is empty now, make the tree an empty tree.
      3. Otherwise (that is, the root is still non-empty):
         1. 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].
         2. Set [math]\displaystyle{ p.n := p.n - 1 }[/math].
      4. Terminate the algorithm and return true
   2. Otherwise, terminate the algorithm and return false.
4. If [math]\displaystyle{ p.n = 1 }[/math]:
   1. If [math]\displaystyle{ p.children[0].n = p.children[1].n = M - 1 }[/math]:
      1. Set [math]\displaystyle{ p.keys[M] := p.keys[1] }[/math].
      2. Set [math]\displaystyle{ p_1 := p.children[0] }[/math] and [math]\displaystyle{ p_2 := p.children[1] }[/math].
      3. Set [math]\displaystyle{ p.children[0] := p_1.children[0] }[/math] and [math]\displaystyle{ p.children[M] := p_2.children[0] }[/math].
      4. For [math]\displaystyle{ j = 1,\dots,M-1 }[/math] set [math]\displaystyle{ p.keys[j] := p_1.keys[j] }[/math], [math]\displaystyle{ p.children[j] := p_1.children[j] }[/math], [math]\displaystyle{ p.keys[M + j] := p_2.keys[j] }[/math], and [math]\displaystyle{ p.children[M + j] := p_2.children[j] }[/math].
      5. Set [math]\displaystyle{ p.n := 2M - 1 }[/math].
   2. Otherwise:
      1. If [math]\displaystyle{ K \leq p.keys[1] }[/math]:
         1. If [math]\displaystyle{ p.children[0].n = M - 1 }[/math], call B-Tree:Shift_Key_to_Sibling with pointer [math]\displaystyle{ p }[/math], index [math]\displaystyle{ 1 }[/math], and [math]\displaystyle{ shiftRight = false }[/math].
         2. If [math]\displaystyle{ p.keys[1] = K }[/math], set [math]\displaystyle{ p' := p }[/math] and [math]\displaystyle{ found := true }[/math].
         3. Set [math]\displaystyle{ p := p.children[0] }[/math].
      2. Otherwise (that is, [math]\displaystyle{ K \gt p.keys[1] }[/math]):
         1. If [math]\displaystyle{ p.children[1].n = M - 1 }[/math], call B-Tree:Shift_Key_to_Sibling with pointer [math]\displaystyle{ p }[/math], index [math]\displaystyle{ 1 }[/math], and [math]\displaystyle{ shiftRight = true }[/math].
         2. If [math]\displaystyle{ p.keys[1] = K }[/math], set [math]\displaystyle{ p' := p }[/math] and [math]\displaystyle{ found = true }[/math].
         3. Set [math]\displaystyle{ p := p.children[1] }[/math].

Proof:

Basically, we have to verify that the implementation invariants of the B-tree data structure and the above-mentioned loop invariants of the removal procedure are fulfilled after the preprocessing.

If the tree is empty (Step 1), the proof is trivial, so consider the case that the tree is non-empty.

Implementation invariants #1, #2, and #8 are trivially fulfilled. Implementation invariants #3, #5, #6, and #7 are guaranteed by Steps 3.1.3 and 4.1.3-5 and by the postconditions of the subroutines called in Step 4.2, respectively. Implementation invariant #4 is guaranteed by Step 3.1.2 and the postconditions of the subroutines called in Step 4, respectively.

The loop invariants of the removal procedure are only affected if Step 4 is executed. Loop invariants #1, #2, and #3 are obvious, #4 does not apply, and #5 is guaranteed by the subroutines called in Step 4.

Obviously, the case distinction in Step 4 covers all possible cases.

Induction Step

Abstract view:

1. If a leaf is reached:
   1. If [math]\displaystyle{ K }[/math] is in that leaf, remove it.
   2. Otherwise, if [math]\displaystyle{ K }[/math] has already been seen, overwrite the found occurrence of [math]\displaystyle{ K }[/math] with its immediate predecessor (which is [math]\displaystyle{ p.keys[p.n] }[/math]).
   3. Terminate the algorithm
2. Otherwise:
   1. Let [math]\displaystyle{ k \in \{0,\dots,p.n\} }[/math] such that [math]\displaystyle{ p.children[k] }[/math] is the next node where to descend.
   2. If [math]\displaystyle{ p.children[k].n = M - 1 }[/math], rearrange the current node at its children appropriately.
   3. Check whether [math]\displaystyle{ K }[/math] is in the current node.

Implementation:

1. If [math]\displaystyle{ p.children[0] = void }[/math] (that is, [math]\displaystyle{ p }[/math] points to aleaf):
   1. If [math]\displaystyle{ K }[/math] is contained in that leaf:
      1. Let [math]\displaystyle{ k \in \{1,\dots,p.n\} }[/math] such that [math]\displaystyle{ p.keys[j-1] := p.keys[j] }[/math].
      2. 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. Remove the key at position [math]\displaystyle{ p.n }[/math] in the node pointed by [math]\displaystyle{ p }[/math].
      4. Set [math]\displaystyle{ p.n := p.n - 1 }[/math].
      5. Terminate the algorithm and return true
   2. Otherwise, if [math]\displaystyle{ found }[/math]:
      1. Let [math]\displaystyle{ k \in \{1,\dots,p'.n\} }[/math] such that [math]\displaystyle{ p'.keys[k] = K }[/math].
      2. Set [math]\displaystyle{ p'.keys[k] := p.keys[p.n] }[/math].
      3. Remove the key at position [math]\displaystyle{ p.n }[/math] in the node pointed by [math]\displaystyle{ p }[/math]
      4. Set [math]\displaystyle{ p.n := p.n - 1 }[/math]
      5. Terminate the algorithm and return true
   3. Otherwise terminate the algorithm and return false
2. Otherwise (that is, [math]\displaystyle{ p }[/math] does not point to a leaf):
   1. If [math]\displaystyle{ K \leq p.keys[1] }[/math], set [math]\displaystyle{ k := 0 }[/math]; otherwise, let [math]\displaystyle{ k \in \{1,\dots,p.n\} }[/math] be maximal such that [math]\displaystyle{ K \gt p.keys[k] }[/math]
   2. If [math]\displaystyle{ p.children[k].n = M - 1 }[/math]:
      1. If [math]\displaystyle{ k = p.n }[/math] (that is, no sibling to the right):
         1. If [math]\displaystyle{ p.children[k-1].n = M - 1 }[/math]: call B-tree: merge two siblings with pointer [math]\displaystyle{ p }[/math] and index [math]\displaystyle{ k }[/math].
         2. Otherwise (that is, [math]\displaystyle{ p.children[k-1].n \gt M -1 }[/math]): call B-Tree:Shift_Key_to_Sibling with pointer [math]\displaystyle{ p }[/math] index [math]\displaystyle{ k }[/math] and [math]\displaystyle{ shiftRight = true }[/math].
      2. Otherwise (that is, [math]\displaystyle{ k \lt p.n }[/math]):
         1. If [math]\displaystyle{ p.children[k+1].n = M - 1 }[/math]: call B-tree: merge two siblings with pointer [math]\displaystyle{ p }[/math] and index [math]\displaystyle{ k + 1 }[/math].
         2. Otherwise (that is, [math]\displaystyle{ p.children[k+1].n \gt M = 1) }[/math]: call B-Tree:Shift_Key_to_Sibling with pointer [math]\displaystyle{ p }[/math] index [math]\displaystyle{ k + 1 }[/math] and [math]\displaystyle{ shiftRight = false }[/math].
   3. If [math]\displaystyle{ K }[/math] is contained in the node to which [math]\displaystyle{ p }[/math] points:
      1. Set [math]\displaystyle{ found = true }[/math]
      2. Set [math]\displaystyle{ p' := p }[/math]
   4. If [math]\displaystyle{ K \leq p.keys[1] }[/math], set [math]\displaystyle{ k := 0 }[/math]; otherwise, let [math]\displaystyle{ k \in \{1,\dots,p.n\} }[/math] be maximal such that [math]\displaystyle{ K \gt p.keys[k] }[/math].
   5. Set [math]\displaystyle{ p := p.children[k] }[/math]

Correctness:

Analogously to the induction basis, we have to verify that the implementation invariants of the B-tree data structure and the above-mentioned loop invariants of the removal procedure are maintained by an iteration of the main loop.

Again, implementation invariants #1 and #2 are trivially fulfilled. In case points to a leaf, implementation invariants #4, #7, and #8 are trivially maintained as well. In this case, Steps 1.1.3 and 1.2.3 guarantee #3, Step 1.1.2 guarantees #5, and Steps 1.1.2 and 4 guarantee #6. In case does not point to a leaf, implementation invariants #3-8 are guaranteed by the subroutines called in Step 2.

Finally, consider the loop invariants of the removal procedure. #1 is trivial; #2 is guaranteed by Step 2.4; #3 and #4.1 by Step 2.3; #4.2 by Step 4, and #5 by the subroutines called in Step 2.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(T\cdot\log n) }[/math] in the best and worst case, where [math]\displaystyle{ T }[/math] is the complexity of the comparison.

Proof: Follows immediately from the facts that

1. [math]\displaystyle{ M }[/math] is assumed to be fixed, and
2. the height of a B-tree with [math]\displaystyle{ n }[/math] nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).

Further Information

In the above specification, each node with exactly [math]\displaystyle{ M - 1 }[/math] keys is modified when visited. This is done for precautionary reasons only. With a slight modification, this can be avoided: when the leaf is reached, go back along the traversed path and modify each nodes with [math]\displaystyle{ M - 1 }[/math] keys until the first node with more than [math]\displaystyle{ M - 1 }[/math] keys is visited. Evidently, this reduces the number of modifications. However, chances are high that these nodes have to be modified sooner or later, so the true benefit is not clear. The version of the removal procedure presented here has primarily been selected because its loop invariant is simpler and more intuitive.