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.
Comments
Post a Comment