Binary search tree: find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with ":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)")
 
 
(26 intermediate revisions by 3 users not shown)
Line 1: Line 1:
:TREE-SEARCH (x, k)
[[Category:Binary_Search_Tree]]
::if x= NIL or k = key[x]
[[Category:Algorithm]]
:::then return x
<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
::if k < key[x]
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree<br>Find</div>
:::then return TREE-SEARCH(left[x], k)
 
::else return TREE-SEARCH(right[x], k)
<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>.
 
'''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 ==
'''Abstract view:''' Set <math>p:=</math> root.
 
'''Implementation:''' Obvious
 
'''Proof:''' Nothing to show
 
== Induction step ==
'''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:'''
# 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)

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)