Why does the AVL tree in Map of OCaml use balance factor (height diff) 2 instead of 1? -

according avl tree wiki

the balance factor calculated follows: balancefactor = height(left-subtree) - height(right-subtree). each node checked, if balance factor remains −1, 0, or +1 no rotations necessary.

however, in ocaml, seems uses balance factor of 2

let bal l x d r =       let hl = match l empty -> 0 | node(_,_,_,_,h) -> h in       let hr = match r empty -> 0 | node(_,_,_,_,h) -> h in       if hl > hr + 2 begin         match l           empty -> invalid_arg "map.bal"         | node(ll, lv, ld, lr, _) ->             if height ll >= height lr               create ll lv ld (create lr x d r)             else begin               match lr                 empty -> invalid_arg "map.bal"               | node(lrl, lrv, lrd, lrr, _)->                   create (create ll lv ld lrl) lrv lrd (create lrr x d r)             end       end else if hr > hl + 2 begin         match r           empty -> invalid_arg "map.bal"         | node(rl, rv, rd, rr, _) ->             if height rr >= height rl               create (create l x d rl) rv rd rr             else begin               match rl                 empty -> invalid_arg "map.bal"               | node(rll, rlv, rld, rlr, _) ->                   create (create l x d rll) rlv rld (create rlr rv rd rr)             end       end else         node(l, x, d, r, (if hl >= hr hl + 1 else hr + 1)) 

why?

in avl trees can see maximal height difference tweakable parameter. must have chosen 2 tradeoff between rebalancing cost on insertion/removal , lookup cost.

since seem interested in these things suggest have @ this paper has formal proof of correctness of ocaml's set's module uses same avl tree, doing did find error in rebalancing scheme... while not strictly equivalent implementation wise, learned quite lot this paper.