Binary search tree: find: Difference between revisions

Latest revision as of 13:38, 3 March 2017

Binary Search Tree
Find

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.

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).
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:

If [math]\displaystyle{ p = }[/math] void, terminate the algorithm and return false.
Otherwise, if [math]\displaystyle{ p }[/math].key [math]\displaystyle{ = K }[/math], terminate the algorithm and return true.
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)

@@ Line 2: / Line 2: @@
 [[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</div>
+<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>
@@ Line 10: / Line 10: @@
 == General Information ==
-'''Algorithmic Problem:''' [[Sorted Sequence:find]]
+'''Algorithmic Problem:''' [[Sorted sequence#Find|Sorted Sequence:find]]
 '''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 ==
 '''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 ==
-'''Abstract view:''' Set '''''p''''':= '''''root'''''.
+'''Abstract view:''' Set <math>p:=</math> root.
 '''Implementation:''' Obvious
@@ Line 31: / Line 34: @@
 == 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:'''
-# 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:
-## 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 ==
-'''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.
-[[File:wcbst.png|300px|thumb|right|Worst case binary search tree]]
 '''Proof:''' Obvious.