F#`Map`算法

Question

F#

Map

类型背后的平衡搜索树实现使用的算法是什么？

https://github.com/dotnet/fsharp/blob/main/src/FSharp.Core/map.fs

我猜它可能是一棵 AVL 树，但我注意到部分代码看起来像

if t2h > t1h + tolerance then

，其中

let tolerance = 2

。我还没有读过代码，但如果它是一棵 AVL 树，我希望容忍度

= 1

.

有趣的是，OCaml 的 LGPL 许可的

Map

模块也有类似

if hl > hr + 2 then begin

的代码：https://github.com/ocaml/ocaml/blob/trunk/stdlib/map.ml