Binary search tree: find: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 14: Line 14:
'''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 '''''p''''' of type "pointer to binary search tree node of type <math>\mathcal{K}</math>".


== Abstract view ==
== Abstract view ==

Revision as of 09:29, 17 May 2015

General Information

Algorithmic Problem: Sorted Sequence:find

Type of algorithm: loop

Auxiliary data: A pointer p 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 p points to a tree node v on height level i (or is void).
  2. The key K is in the range of v.

Variant: i is increased by 1.

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

Induction basis

Abstract view: Set p:= 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:

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

Correctnes: Obvious.

Complexity

Statement: Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).

Worst case binary search tree

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)