1
(* $Id: avlTree.ml,v 1.2 2003/06/08 04:50:48 yori Exp $ *)
2
(* Copyright 2003 Yamagata Yoriyuki. distributed with LGPL *)
4
type 'a tree = Empty | Node of 'a tree * 'a * 'a tree * int
8
let is_empty = function Empty -> true | _ -> false
10
let singleton_tree x = Node (Empty, x, Empty, 1)
12
let left_branch = function
13
Empty -> raise Not_found
14
| Node (l, _, _, _) -> l
16
let right_branch = function
17
Empty -> raise Not_found
18
| Node (_, _, r, _) -> r
21
Empty -> raise Not_found
22
| Node (_, v, _, _) -> v
26
| Node (_, _, _, h) -> h
29
let h' = 1 + max (height l) (height r) in
32
let rec make_tree l v r =
38
| Node (ll, u, lr, _) ->
39
create ll u (make_tree lr v r)
40
else if hr >= hl + 2 then
43
| Node (rl, u, rr, _) ->
44
create (make_tree l v rl) u rr
49
let rec split_leftmost = function
50
Empty -> raise Not_found
51
| Node (Empty, v, r, _) -> (v, r)
52
| Node (l, v, r, _) ->
53
let v0, l' = split_leftmost l in
54
(v0, make_tree l' v r)
56
let rec split_rightmost = function
57
Empty -> raise Not_found
58
| Node (l, v, Empty, _) -> (v, l)
59
| Node (l, v, r, _) ->
60
let v0, r' = split_rightmost r in
61
(v0, make_tree l v r')
63
let rec concat t1 t2 =
67
| Node (l1, v1, r1, h1), Node (l2, v2, r2, h2) ->
69
make_tree (concat t1 l2) v2 r2
71
make_tree l1 v1 (concat r1 t2)
73
let rec iter proc = function
75
| Node (l, v, r, _) ->
80
let rec fold f t init =
83
| Node (l, v, r, _) ->
84
let x = fold f l init in
added
removed
internal/avlTree.ml
