View source for Binary search tree: find

[[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 ==

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

'''Type of algorithm:''' loop

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

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

== Induction basis ==
'''Abstract view:''' Set <math>p:=</math> root.

'''Implementation:''' Obvious

'''Proof:''' Nothing to show

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

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

'''Correctness:''' Obvious.

== Complexity ==
'''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.

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