B-tree: find: Difference between revisions
(Created page with "== General Information == == Abstract View == == Induction Basis == == Induction Step == == Complexity ==") |
|||
(32 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Videos]] | |||
{{#ev:youtube|https://www.youtube.com/watch?v=vbRZ8h6ROYc|500|right||frame}} | |||
[[Category:B-Tree]] | |||
[[Category:Algorithm]] | |||
== General Information == | == General Information == | ||
'''Algorithmic problem:''' [[Sorted sequence#Find|Sorted sequence: find]] | |||
'''Type of algorithm:''' loop | |||
'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to a B-tree node of key type <math>\mathcal{K}</math>". | |||
== Abstract View == | == Abstract View == | ||
'''Invariant:''' After <math>i\geq 0</math> iterations: | |||
# pointer <math>p</math> points to some node of the B-tree on height level <math>i</math> and | |||
# the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that node. | |||
'''Variant:''' <math>i</math> is increased by <math>1</math>. | |||
'''Break condition:''' | |||
# <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. | |||
'''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 == | ||
'''Abstract view:''' '''''p''''' is initialized so as to point to the root of the B-tree. | |||
'''Implementation:''' Obvious. | |||
'''Proof:''' Obvious. | |||
== Induction Step == | == Induction Step == | ||
'''Abstract view:''' | |||
# Let <math>N</math> denote the node to which <math>p</math> currently points. | |||
# If the searched key is in <math>N</math>, terminate the algorithm and return '''true'''. | |||
# Otherwise, if <math>N</math> is a leaf, terminate the algorithm and return '''false'''. | |||
# Otherwise, let <math>p</math> point the child of <math>N</math> such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child. | |||
'''Implementation:''' | |||
# If <math>K</math> is one of the values <math>p</math>.keys<math>[1],\dots,p</math>.keys<math>[p.n]</math>, terminate the algorithm and return '''true'''. | |||
# If <math>p</math>.children<math>[0] =</math> void (that is, the current node is a leaf), terminate the algorithm and return '''false'''. | |||
# If <math>K < p</math>.keys<math>[1]</math> set <math>p := p</math>.children<math>[0]</math>. | |||
# Otherwise, if <math>K > p</math>.keys<math>[p.n]</math> set <math>p := p</math>.children<math>[p.n]</math>. | |||
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p</math>.keys<math>[i] < K < p</math>.keys<math>[i+1]</math>. | |||
# Set <math>p := p</math>.children<math>[i]</math>. | |||
'''Correctness:''' | |||
Obvious. | |||
== Complexity == | == 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 == | |||
<code> | |||
B-TREE-FIND(''x,k'') | |||
1 ''i'' = 1 | |||
2 '''while''' i ≤ ''x.n'' and ''k'' > ''x.key<sub>i</sub>'' | |||
3 ''i'' = ''i'' + 1 | |||
4 '''if''' ''i'' ≤ ''x.n'' and ''k'' == ''x.key<sub>i</sub>'' | |||
5 '''return''' (''x.i'') | |||
6 '''elseif''' '' x.leaf'' | |||
7 '''return''' NIL | |||
8 '''else''' DISK-READ(''x.c<sub>i</sub>'') | |||
9 '''return''' B-TREE-FIND(''x.c<sub>i</sub>,k'') | |||
</code> |
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:
- pointer [math]\displaystyle{ p }[/math] points to some node of the B-tree on height level [math]\displaystyle{ i }[/math] and
- the searched key is in the range of that node.
Variant: [math]\displaystyle{ i }[/math] is increased by [math]\displaystyle{ 1 }[/math].
Break condition:
- [math]\displaystyle{ 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]\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:
- Let [math]\displaystyle{ N }[/math] denote the node to which [math]\displaystyle{ p }[/math] currently points.
- If the searched key is in [math]\displaystyle{ N }[/math], terminate the algorithm and return true.
- Otherwise, if [math]\displaystyle{ N }[/math] is a leaf, terminate the algorithm and return false.
- 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:
- 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.
- 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.
- If [math]\displaystyle{ K \lt p }[/math].keys[math]\displaystyle{ [1] }[/math] set [math]\displaystyle{ p := p }[/math].children[math]\displaystyle{ [0] }[/math].
- 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].
- 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].
- 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 i ≤ x.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)