Binary search tree: find

From Algowiki
Jump to: navigation, search

General Information

Algorithmic Problem: 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.

  1. The pointer [math]p[/math] points to a tree node [math]v[/math] on height level [math]i[/math] (or is void).
  2. The key [math]K[/math] is in the 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:

  1. If [math]p =[/math] void, terminate the algorithm and return false.
  2. Otherwise, if [math]p[/math].key [math]= K[/math], terminate the algorithm and return true.
  3. Otherwise:
    1. If [math]K \lt p[/math].key, set [math]p :=[/math]left.
    2. If [math]K \gt 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)