5

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

为什么？

4

1 回答 1

8

在 AVL 树中，您可以将最大高度差视为可调整的参数。他们必须选择 2 来权衡插入/移除的重新平衡成本和查找成本。

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

于 2013-08-10T16:06:45.653 回答