B-tree: find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[Category:Checkup]]
[[Category:Videos]]
 
{{#ev:youtube|https://www.youtube.com/watch?v=vbRZ8h6ROYc|500|right||frame}}
[[Category:B-Tree]]
[[Category:B-Tree]]
[[Category:Algorithm]]
[[Category:Algorithm]]
Line 20: Line 20:
# <math>p</math> points to a leaf of the B-tree or (that is, inclusive-or)
# <math>p</math> points to a leaf of the B-tree or (that is, inclusive-or)
# the searched key is in the node to which <math>p</math> points.
# the searched key is in the node to which <math>p</math> points.
'''Remark:''' For example, the height of the subtree rooted at the node to which <math>p</math> points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.


== Induction Basis ==
== Induction Basis ==
Line 27: Line 29:


'''Proof:''' Obvious.
'''Proof:''' Obvious.


== Induction Step ==
== Induction Step ==
Line 47: Line 48:
'''Correctness:'''
'''Correctness:'''
Obvious.
Obvious.
== Complexity ==
'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot\log n)</math> in the worst case, where <math>T</math> is the complexity of the comparison and <math>n</math> the total number of keys in the B-tree.
'''Proof:''' Follows immediately from the the [[B-tree#Depth of a B-tree|maximum height]] of the B-tree.


== Pseudocode ==  
== Pseudocode ==  
Line 61: Line 68:
  9        '''return''' B-TREE-FIND(''x.c<sub>i</sub>,k'')
  9        '''return''' B-TREE-FIND(''x.c<sub>i</sub>,k'')
</code>
</code>
== Complexity ==
'''Statement:''' The asymptotic complexity is in <math>\Theta(T\cdot\log n)</math> in the worst case, where <math>T</math> is the complexity of the comparison.
'''Proof:''' Follows immediately from the fact that the height of B-tree with <math>n</math> nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).

Latest revision as of 13:46, 3 March 2017

General Information

Algorithmic problem: Sorted sequence: find

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to a B-tree node of key type [math]\displaystyle{ \mathcal{K} }[/math]".

Abstract View

Invariant: After [math]\displaystyle{ i\geq 0 }[/math] iterations:

  1. pointer [math]\displaystyle{ p }[/math] points to some node of the B-tree on height level [math]\displaystyle{ i }[/math] and
  2. the searched key is in the range of that node.

Variant: [math]\displaystyle{ i }[/math] is increased by [math]\displaystyle{ 1 }[/math].

Break condition:

  1. [math]\displaystyle{ p }[/math] points to a leaf of the B-tree or (that is, inclusive-or)
  2. the searched key is in the node to which [math]\displaystyle{ p }[/math] points.

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: p is initialized so as to point to the root of the B-tree.

Implementation: Obvious.

Proof: Obvious.

Induction Step

Abstract view:

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

Implementation:

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

Correctness: Obvious.

Complexity

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

Proof: Follows immediately from the the maximum height of the B-tree.

Pseudocode

B-TREE-FIND(x,k)
1 i = 1
2 while i ≤ x.n and k > x.keyi 
3        i = i + 1
4 if ix.n and k == x.keyi 
5        return (x.i)
6 elseif  x.leaf
7        return NIL
8 else DISK-READ(x.ci) 
9        return B-TREE-FIND(x.ci,k)