(************************************************************************)
(* Datatypes: Binary Trees *)
(* Binary trees are one of the most common data-structures used.
Copyright By PowCoder代写 加微信 powcoder
Inductive definition of binary trees:
o The empty binary tree “Empty” is a binary tree.
o If l and r are binary trees and v is a value of type ‘a
then Node (v, l, r) is a binary tree.
o Nothing else is a binary tree.
(************************************************************************)
type ‘a tree = Empty | Node of ‘a * ‘a tree * ‘a tree
(* size of a tree
size: ‘a tree -> int
size(T) = n where n is size of the tree determined by
the number of nodes.
let rec size t = match t with
| Empty -> 0
| Node (a, l, r) -> size l + size r + 1
(* Food-for thought question:
1) How could we define an n-ary tree?
2) How could one define a red-black tree?
(* insert: ‘a * ‘b -> (‘a * ‘b) tree -> (‘a * ‘b) tree
insert (x,d) T = T’ where (x,d) has been inserted into T
and any previous occurrences of (x,d’) in T have been
overwritten
let rec insert ((x,d) as e) t = match t with
| Empty -> Node(e, Empty, Empty)
| Node ((y,d’), l, r) ->
if x = y then Node(e, l, r)
(if x < y then Node((y,d'), insert e l, r)
Node((y,d'), l, insert e r))
(* NOTE: Although the type of the function insert is polymorphic
in 'a and 'b, it depends on the fact that we do have functions
to compare elements of type 'a!
(* Remark about comparison operators.
= and < are meaningful for numbers, strings, and characters.
BUT in OCaml you can also compare any other object; this is
to be used cautiously, since it may or may not reflect your
intended meaning of less or equal.
For example: The following looks entirely reasonable and
is accepted by OCaml.
# Empty < Node (3, Empty, Empty);;
- : bool = true
# Node (3, Empty, Empty) < Node (4, Empty, Empty);;
- : bool = true
# Node (3, Empty, Empty) < Node (2, Empty, Empty);;
- : bool = false
However, the following is also accepted.
# [3;4] < [7];;
- : bool = true
# [3;4] < [2];;
- : bool = false
# [3;3;4] < [6;7;4];;
- : bool = true
# [3;3;4] < [1;7;4];;
- : bool = false
Clearly, OCaml compares the lists by comparing their elements;
but it does not take into account the length of the list.
For better, more readable and easier to understand code, we recommend
you write out equality definition explicitely. In fact, some languages
do not allow you to compare data constructed from constructors via
built-in operators such as = or <.
(* lookup : 'a -> (‘a * ‘b) tree -> ‘b option
lookup x T =
if there exists a node in T with key x and data d,
then return Some(d) else None
NOTE: Although the type of this function is polymorphic
in ‘a and ‘b, it depends on the fact that we do have
functions to compare elements of type ‘a!
let rec lookup x t = match t with
| Empty -> None
| Node ((y,d), l, r) ->
if x = y then Some(d)
(if x < y then lookup x l
else lookup x r)
(* NOTE: We enforce the following property :
lookup x (insert (x,d) t) = Some (d)
Case t = Empty
lookup x (insert (x,dx) Empty)
==> lookup x (Node ( (x,dx), Empty, Empty)
==> Some dx
Case t = Node ( (y,dy), l, r)
IH 1: lookup x (insert (x,dx) l) ==> Some dx
IH 2: lookup x (insert (x,dx) r) ==> Some dx
TO SHOW: lookup x (insert (x, dx) (Node ( (y, dy), l , r))) ==> Some dx
lookup x (insert (x, dx) (Node ( (y, dy), l , r)))
==> lookup x (Node ( (x, dx) , l, r) ==> Some dx
lookup x (insert (x, dx) (Node ( (y, dy), l , r)))
==> lookup x (Node ( (y, dy), insert (x, dx) l , r))
==> lookup x (insert (x,dx) l) ==IH==> Some dx
lookup x (insert (x, dx) (Node ( (y, dy), l , r)))
==> lookup x (Node ( (y, dy), l, insert (x, dx) r))
==> lookup x (insert (x,dx) r) ==IH==> Some dx
(************************************************************************)
(* Examples of trees *)
let t1 = Node(9, Node(3, Node(2, Empty, Empty),
Node(5, Node(4, Empty, Empty), Node(6, Empty, Empty))),
Node(13, Node(11, Empty, Empty), Node(15, Empty, Empty)));;
(* 9
3 13
/ \ / \
2 5 11 15
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com