为什么OCaml Map中的AVL树使用平衡因子(height diff)2而不是1？

Question

根据AVL树维基

平衡因子计算如下:balanceFactor = height(left-subtree) - height(right-subtree).对于检查的每个节点,如果平衡因子保持-1,0或+1,则不需要旋转.

但是,在OCaml中,它似乎使用平衡因子2

let bal l x d 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 "Map.bal"
        | Node(ll, lv, ld, lr, _) ->
            if height ll >= height lr then
              create ll lv ld (create lr x d r)
            else begin
              match lr with
                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 then begin
        match r with
          Empty -> invalid_arg "Map.bal"
        | Node(rl, rv, rd, rr, _) ->
            if height rr >= height rl then
              create (create l x d rl) rv rd rr
            else begin
              match rl with
                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 then hl + 1 else hr + 1))

为什么？

Answer 1

在AVL树中,您可以将最大高度差看作可调整参数.他们必须选择2来在插入/移除的重新平衡成本和查找成本之间进行权衡.

既然你似乎对这些东西感兴趣,我建议你看看这篇论文,它正确证明了OCaml的Set模块的正确性,该模块使用相同的AVL树,通过这样做,他们实际上确实在重新平衡方案中发现错误...虽然没有严格等同的实施方式,但我从本文中学到了很多东西.