Tại sao cây AVL trong Bản đồ OCaml sử dụng hệ số cân bằng (chiều cao chênh lệch) 2 thay vì 1?

Question

Theo AVL tree wiki

Yếu tố cân bằng được tính như sau: balanceFactor = chiều cao (trái cây con) - Chiều cao (phải cây con). Đối với mỗi nút được chọn, nếu hệ số cân bằng vẫn −1, 0 hoặc +1 thì không cần quay.

Tuy nhiên, trong OCaml, có vẻ như nó sử dụng yếu tố cân bằng của 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)) 

Tại sao?

Answer 1

Trong cây AVL, bạn có thể thấy sự chênh lệch độ cao tối đa làm tham số có thể điều chỉnh. Họ phải chọn 2 để cân bằng giữa chi phí tái cân bằng khi chèn/xóa và chi phí tra cứu.

Vì bạn có vẻ quan tâm đến những điều này, tôi khuyên bạn nên xem this paper có bằng chứng chính xác về tính chính xác của mô-đun Set của OCaml sử dụng cùng một cây AVL, bằng cách làm như vậy họ thực sự đã tìm thấy lỗi kế hoạch tái cân bằng ... Ngoài ra trong khi không thực hiện tương đương nghiêm túc khôn ngoan, tôi đã học được khá nhiều từ điều này this paper.