Balancing algorithm of Set/Map implementation

[Yoriyuki Yamagata <yoriyuki.y@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1888 bytes --]

Hi, list.

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))

I have two question.

        | Node(ll, lv, lr, _) ->
            if height ll >= height lr then
              create ll lv (create lr v r)
            else begin

Is this code right?  If r is Empty and lr and ll are huge trees,
doesn't it create a massively unbalanced tree?

Another question is that why OCaml implementation allows
a balancing factor up to *2*, which is usually allowed only up to 1?

Maybe my question is naive one, but I would appreciate if your could comment it.

Regards,

-- 
Yoriyuki Yamagata
yoriyuki.y@gmail.com

[-- Attachment #2: Type: text/html, Size: 2246 bytes --]