OCaml中map.ml中的平衡bst是如何實現的？

Question

我只是來看看map.ml OCaml中的源代碼：https://github.com/MassD/ocaml/blob/master/stdlib/map.ml

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

看來平衡不是red-black-tree和許多簡單得多。

在OCaml中，balancing的map.ml裏面的soul是什麼？

Answer 1

set.ml和map.ml使用AVL樹木。