Binary search tree: find

Binary Search Tree
Find

Sorted sequence

Openlearnware
See Chapter 2,3

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)