5

AVLツリーウィキによると

バランス ファクターは次のように計算されます。チェックされた各ノードについて、バランス係数が -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 のセットのモジュールの正しさの正式な証明が記載されているこの論文を参照することをお勧めします。そうすることで、実際にリバランス スキームにエラーが見つかりました。 ...また、厳密に同等の実装ではありませんが、この論文から多くのことを学びました。

于 2013-08-10T16:06:45.653 に答える