On 2010-05-14 08:17, Yoriyuki Yamagata wrote:
> When I read the balancing function of stdlib's Set/Map several years
> ago, I thought I have understand how it works. But now, I read it again
> and I'm less confident now. Could someone answer my questions? Here is
> the snippet of the code.
>
> let bal l v r =
> let hl = match l with Empty -> 0 | Node(_,_,_,h) -> h in
> let hr = match r with Empty -> 0 | Node(_,_,_,h) -> h in
> if hl > hr + 2 then begin
> match l with
>
> Empty -> invalid_arg "Set.bal"
> | Node(ll, lv, lr, _) ->
> if height ll >= height lr then
> create ll lv (create lr v r)
> else begin
> match lr with
>
> Empty -> invalid_arg "Set.bal"
> | Node(lrl, lrv, lrr, _)->
> create (create ll lv lrl) lrv (create lrr v r)
> end
> end else if hr > hl + 2 then begin
>
> match r with
> Empty -> invalid_arg "Set.bal"
> | Node(rl, rv, rr, _) ->
> if height rr >= height rl then
> create (create l v rl) rv rr
> else begin
>
> match rl with
> Empty -> invalid_arg "Set.bal"
> | Node(rll, rlv, rlr, _) ->
> create (create l v rll) rlv (create rlr rv rr)
> end
>
> end else
> Node(l, v, r, (if hl >= hr then hl + 1 else hr + 1))
[...]
> Another question is that why OCaml implementation allows
> a balancing factor up to *2*, which is usually allowed only up to 1?
I guess the balancing factor of -2/+2 can only occur temporarily
during insert/delete operations (and such). See for instance (set.ml):
let rec add x = function
Empty -> Node(Empty, x, Empty, 1)
| Node(l, v, r, _) as t ->
let c = Ord.compare x v in
if c = 0 then t else
if c < 0 then bal (add x l) v r else bal l v (add x r)
let rec remove x = function
Empty -> Empty
| Node(l, v, r, _) ->
let c = Ord.compare x v in
if c = 0 then merge l r else
if c < 0 then bal (remove x l) v r else bal l v (remove x r)
This is what bal is for: to fix the balance in the tree root.
I guess this: http://en.wikipedia.org/wiki/AVL_tree#Operations is
more or less correct. :-)
STF
http://eisenbits.homelinux.net/~stf/
OpenPGP: DFD9 0146 3794 9CF6 17EA D63F DBF5 8AA8 3B31 FE8A
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
