B-tree: insert and rearrange: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 30: Line 30:
== Induction Step ==
== Induction Step ==
'''Abstract view:'''
'''Abstract view:'''
# Let '''''N''''' denote the node to which '''''p''''' currently points.
# If the node is not full, the key can be inserted, and we are done.
# If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''.
## If the new key is larger than all keys stored in the node, it can be appended.
# Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''.
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.
# Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.
## <math>N_1</math>  will contain all keys strictly less than the median of <math>{p</math>.keys<math>[1], ... , p.</math>keys<math>[p.n], K'}


'''Implementation:'''
'''Implementation:'''

Revision as of 16:31, 30 September 2014

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. If the node is not full, the key can be inserted, and we are done.
    1. If the new key is larger than all keys stored in the node, it can be appended.
    2. Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.
  2. On the other hand, if the node is indeed full, the key cannot be inserted. In this case:
    1. The current node [math]\displaystyle{ N }[/math] will be split into two nodes, [math]\displaystyle{ N_1 }[/math] and [math]\displaystyle{ N_2 }[/math].
    2. [math]\displaystyle{ N_1 }[/math] will contain all keys strictly less than the median of [math]\displaystyle{ {p }[/math].keys[math]\displaystyle{ [1], ... , p. }[/math]keys[math]\displaystyle{ [p.n], K'} '''Implementation:''' # If '''''K''''' is one of the values \lt math\gt p.keys[1],\dots,p.keys[p.n] }[/math], terminate the algorithm and return true.
  3. If [math]\displaystyle{ p.children[0] = void }[/math] (that is, the current node is a leaf), terminate the algorithm and return false.
  4. If [math]\displaystyle{ K \lt p.keys[1] }[/math] set [math]\displaystyle{ p := p.children[p.n] }[/math].
  5. Otherwise, if [math]\displaystyle{ K \gt p.keys[p.n]\lt /math set \lt math\gt p := p.children[p.n] }[/math].
  6. 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].
  7. 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).