Binary search tree: find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(22 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Category:Binary_Search_Tree]]
[[Category:Algorithm]]
<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree<br>Find</div>
<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">[[Sorted sequence]]</div>
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/binary-search-tree-1938 Openlearnware]<br>See Chapter 2,3</div>
</div>
== General Information ==
== General Information ==


'''Algorithmic Problem:''' [[Sorted Sequence:find]]
'''Algorithmic Problem:''' [[Sorted sequence#Find|Sorted Sequence:find]]


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


'''Auxiliary data:'''  A pointer '''''p''''' of type "pointer to binary search tree node of type <math>\kappa</math>".
'''Auxiliary data:'''  A pointer <math>p</math> of type "pointer to binary search tree node of type <math>\mathcal{K}</math>."


== Abstract view ==
== Abstract view ==
'''Invariant:''' After <math>i\geq 0</math> Iterations.
'''Invariant:''' After <math>i\geq 0</math> Iterations.
# The pointer '''''p''''' points to a tree node '''''v''''' on height level '''''i''''' (or is void).  
# The pointer <math>p</math> points to a tree node <math>v</math> on height level <math>i</math> (or is void).  
# The key '''''K''''' is in the range of '''''v'''''.
# The key <math>K</math> is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of <math>v</math>.
'''Variant:''' '''''i''''' is increased by 1.
'''Variant:''' <math>i</math> is increased by 1.
 
'''Break condition:''' Either it is <math>p =</math>void or, otherwise,  it is <math>p</math>.key <math>= K</math>.
 
'''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.


'''Break condition:''' Either it is <math>p = void</math> or, otherwise, <math>p.key = K</math>.
== Induction basis ==
== Induction basis ==
'''Abstract view:''' Set '''''p''''':= '''''root'''''.
'''Abstract view:''' Set <math>p:=</math> root.


'''Implementation:''' Obvious
'''Implementation:''' Obvious
Line 22: Line 34:


== Induction step ==
== Induction step ==
'''Abstract view:''' If '''''p''''' points to a node but not with key '''''K''''', '''''p''''' descends in the appropriate direction, left or right.
'''Abstract view:''' If <math>p</math> points to a node but not with key <math>K</math>, <math>p</math> descends in the appropriate direction, left or right.


'''Implementation:'''
'''Implementation:'''
# If <math>p = void</math>, terminate the algorithm and return '''''false'''''.
# If <math>p =</math> void, terminate the algorithm and return '''false'''.
# Otherwise, if <math>p.key = K</math>, terminate the algorithm and return '''''true'''''.
# Otherwise, if <math>p</math>.key <math>= K</math>, terminate the algorithm and return '''true'''.
# Otherwise:
# Otherwise:
## If <math>K < p.key</math>, set <math>p := left</math>.
## If <math>K < p</math>.key, set <math>p :=</math>left.
## If <math>K > p.key</math>, set <math>p := right</math>.
## If <math>K > p</math>.key, set <math>p :=</math> right.


'''Correctnes:''' Obvious.
'''Correctness:''' Obvious.


== Complexity ==
== Complexity ==
'''Statement:''' Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).
'''Statement:''' The complexity is in <math>\mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n)</math> in the worst case, where <math>n</math> is the length of the sequence, <math>h</math> the height of the tree, and <math>T</math> the complexity of the comparison.


'''Proof:''' Obvious.
'''Proof:''' Obvious.
Line 45: Line 57:
::then return TREE-SEARCH(left[x], k)
::then return TREE-SEARCH(left[x], k)
:else return TREE-SEARCH(right[x], k)
:else return TREE-SEARCH(right[x], k)
[[Category:Binary_Search_Tree]]

Latest revision as of 13:38, 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 binary search tree node of type [math]\displaystyle{ \mathcal{K} }[/math]."

Abstract view

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

  1. The pointer [math]\displaystyle{ p }[/math] points to a tree node [math]\displaystyle{ v }[/math] on height level [math]\displaystyle{ i }[/math] (or is void).
  2. The key [math]\displaystyle{ K }[/math] is in the range of [math]\displaystyle{ v }[/math].

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

Break condition: Either it is [math]\displaystyle{ p = }[/math]void or, otherwise, it is [math]\displaystyle{ p }[/math].key [math]\displaystyle{ = K }[/math].

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: Set [math]\displaystyle{ p:= }[/math] root.

Implementation: Obvious

Proof: Nothing to show

Induction step

Abstract view: If [math]\displaystyle{ p }[/math] points to a node but not with key [math]\displaystyle{ K }[/math], [math]\displaystyle{ p }[/math] descends in the appropriate direction, left or right.

Implementation:

  1. If [math]\displaystyle{ p = }[/math] void, terminate the algorithm and return false.
  2. Otherwise, if [math]\displaystyle{ p }[/math].key [math]\displaystyle{ = K }[/math], terminate the algorithm and return true.
  3. Otherwise:
    1. If [math]\displaystyle{ K \lt p }[/math].key, set [math]\displaystyle{ p := }[/math]left.
    2. If [math]\displaystyle{ K \gt p }[/math].key, set [math]\displaystyle{ p := }[/math] right.

Correctness: Obvious.

Complexity

Statement: The complexity is in [math]\displaystyle{ \mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n) }[/math] in the worst case, where [math]\displaystyle{ n }[/math] is the length of the sequence, [math]\displaystyle{ h }[/math] the height of the tree, and [math]\displaystyle{ T }[/math] the complexity of the comparison.

Proof: Obvious.

Pseudocode

TREE-SEARCH (x, k)

if x= NIL or k = key[x]
then return x
if k < key[x]
then return TREE-SEARCH(left[x], k)
else return TREE-SEARCH(right[x], k)