I have the following three version of the search operation over the binary tree (not ordering).
Given:
type 'a btree =
| Empty
| Node of 'a * 'a btree * 'a btree;;
I have:
1.
let rec bsearch x tree =
match tree with
| Empty -> Empty
| Node (root, left, right) ->
if (root = x) then tree else
match left with
| Empty -> bsearch x right
| Node (_, left, _) -> bsearch x left;;
let rec bsearch x tree =
match tree with
| Empty -> Empty
| Node (root, left, right) when x = root -> tree
| Node (_, left, right) ->
match left with
| Empty -> bsearch x right
| t -> bsearch x t;;
let rec bsearch x t =
match t with
| Empty -> Empty
| Node(a, left, right) ->
if a = x then t
else
match bsearch x left with
| Empty -> bsearch x right
| t' -> t'
Assuming these are equivalent, having the same time complexity, and except the last one not being tail recursive, what is the big difference between them? I also find the last line in 3.:
| t' -> t'
to never be used. Is it correct that the last one is the least efficient of all three versions.
If the node does not contain the value we're looking for, then we check to see if the left branch is Empty. If it is, we search the right branch. That makes sense.
If it's not though, then we immediately search the left branch node's left branch. We've skipped a node.
Let's consider a very simple tree. No right branches at all.
--5
/
-3
/
1
If we're searching for 3, then this considers 5 and finds it doesn't equal 3. The left branch isn't Empty but rather Node (3, Node (1, Empty, Empty), Empty) so it evaluates bsearch 3 (Node (1, Empty, Empty), Empty)). This node isn't Empty, the value doesn't match, but the left branch is Empty, so we search the right branch. The right branch is Empty, so the result is Empty.
What happens here if the value we're looking for isn't found in the left branch? Consider again a sample tree.
-----5-----
/ \
---3--- ---7---
/ \ / \
2 4 6 8
We search for 6. We should get Node (6, Empty, Empty).
5 isn't right, and the left branch isn't Empty, so we search it.
3 isn't right, and the left branch isn't Empty, so we search it.
2 isn't right, but the left branch is Empty, so we search the right branch. That's Empty too, so the result is Empty.
Let's rerun that last example tree search with this function.
5 isn't right, so we search the left branch.
3 isn't right, so we search the left branch.
2 isn't right, so we search the left branch.
The left branch is Empty so we get Empty back. Because that returned Empty we search the right branch. The right branch is Empty so we get Empty back.
We now search the right branch of Node (3, Node (2, Empty, Empty), Node (4, Empty, Empty)). We know this will return Empty and we'll end up searching Node (7, Node (6, Empty, Empty), Node (8, Empty, Empty)).
7 isn't right, so we search the left branch.
6 is correct, so we return Node (6, Empty, Empty).
Function 3 is correct, and has a time complexity of O(n). The time complexities of the other two functions are somewhat moot as they do not return correct results.
In function 3, that last line | t' -> t' is used when bsearch x left returns a Node rather than Empty.
As noted in a previous answer on this subject, a "worklist" based approach to this problem, where right branches are added to a list of nodes to process not only handles searching the entire tree (in a depth-first manner), but eliminates the tail-recursion.
let search x t =
let rec search' x t stack =
match t, stack with
| Empty, [] -> Empty
| Empty, n::ns -> search' x n ns
| Node (v, _, _), _ when x = v -> t
| Node (_, l, r), _ -> search' x l @@ r :: stack
in
search' x t []