B-tree: insert and rearrange

General Information

Algorithmic problem: Text here

Type of algorithm: Text

Auxiliary data:

1. Three pointers [math]\displaystyle{ p, p_1, p_2 }[/math] or type "pointer to B-tree node".
2. A current key [math]\displaystyle{ K' \in K }[/math]

Abstract View

Invariant: Before and after each iteration, [math]\displaystyle{ p }[/math] points to a node [math]\displaystyle{ N }[/math] such that the following holds:

1. In the case [math]\displaystyle{ p.n \lt 2M }[/math], all implementation invariants of B-trees are maintained if the following [math]\displaystyle{ K' }[/math] can be inserted at some position in [math]\displaystyle{ N }[/math] such that after insertion.
2. In the case [math]\displaystyle{ p.n = 2M }[/math], imagine that we could extend [math]\displaystyle{ p }[/math].keys by one more slot (and, consequently, extend .successors by one more slot). Then [math]\displaystyle{ K' }[/math] can be inserted in [math]\displaystyle{ N }[/math] at a position such that - except for the statement about the size of [math]\displaystyle{ N }[/math] - all implementation invariants of B-trees are again maintained after insertion.

Variant: The height level of the node to which [math]\displaystyle{ p }[/math] points is decreased by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ p.N \lt 2M }[/math] or (that is, inclusive-or) [math]\displaystyle{ p }[/math] points to the root.

Induction Basis

Abstract view:

1. [math]\displaystyle{ p }[/math] is set to the input pointer.
2. [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] are void initially.

Implementation: Obvious.

Proof: The requirement on the input pointer immediately implies the invariants.

Induction Step

Abstract view:

1. Let N denote the node to which p currently points.
2. If the searched key is in N, terminate the algorithm and return true.
3. Otherwise, if N is a leaf, terminate the algorithm and return false.
4. Otherwise, let p point the child of N such that the searched key is in the range of that child

Implementation:

1. If K is one of the values [math]\displaystyle{ p.keys[1],\dots,p.keys[p.n] }[/math], terminate the algorithm and return true.
2. If [math]\displaystyle{ p.children[0] = void }[/math] (that is, the current node is a leaf), terminate the algorithm and return false.
3. If [math]\displaystyle{ K \lt p.keys[1] }[/math] set [math]\displaystyle{ p := p.children[p.n] }[/math].
4. Otherwise, if [math]\displaystyle{ K \gt p.keys[p.n]\lt /math set \lt math\gt p := p.children[p.n] }[/math].
5. Otherwise, there is exactly one [math]\displaystyle{ i \in \{1,\dots,p.n-1\} }[/math] such that [math]\displaystyle{ p.keys[i] \lt K \lt p.keys[i+1] }[/math].
6. Set [math]\displaystyle{ p := p.children[i] }[/math].

Correctness: Obvious.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(\log n) }[/math] in the worst case.

Proof: Follows immediately from the fact that the height of B-tree with n nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).