B-tree: find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 11: Line 11:
'''Invariant:''' Before and after each iteration:
'''Invariant:''' Before and after each iteration:
# '''''p''''' points to some node '''''N''''' of the B-tree and
# '''''p''''' points to some node '''''N''''' of the B-tree and
# the searched key is in the [[Directed tree|range]] of '''''N'''''.
# the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''N'''''.


'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to some child of the current node.
'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to some child of the current node.

Revision as of 18:52, 29 September 2014

General Information

Algorithmic problem: Sorted sequence: find

Type of algorithm: loop

Auxiliary data: A pointer p of type "pointer to a B-tree node".

Abstract View

Invariant: Before and after each iteration:

  1. p points to some node N of the B-tree and
  2. the searched key is in the range of N.

Variant: p is redirected from the current node N to some child of the current node.

Break condition:

  1. p points to a leaf of the B-tree or (that is, inclusive-or)
  2. the searched key is in the node to which p points.

Induction Basis

Abstract view: p is initialized so as to point to the root of the B-tree.

Implementation: Obvious.

Proof: Obvious.

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).