最近，我正在阅读《纯功能数据结构》一书
当我进入Leftist_tree的“练习3.2直接定义插入而不是通过合并调用”时。我实现了我的版本插入。
let rec insert x t =
try
match t with
| E -> T (1, x, E, E)
| T (_, y, left, right ) ->
match (Elem.compare x y) with
| n when n < 0 -> makeT x left (insert y right)
| 0 -> raise Same_elem
| _ -> makeT y left (insert x right)
with
Same_elem -> t
为了验证它是否有效，我对其进行了测试以及本书提供的合并功能。
let rec merge m n = match (m, n) with
| (h, E) -> h
| (E, h) -> h
| (T (_, x, a1, b1) as h1, (T (_, y, a2, b2) as h2)) ->
if (Elem.compare x y) < 0
then makeT x a1 (merge b1 h2)
else makeT y a2 (merge b2 h1)
然后我发现了一件有趣的事情。
我使用列表
["a";"b";"d";"g";"z";"e";"c"]作为创建此树的输入。并且两个结果是不同的。对于合并方法，我得到了像这样的树：
我实现的插入方法给我像这样的树：
我认为尽管我遵循“合并”的实现来设计“插入”版本，但两种方法之间还是有一些细节。但是，然后我尝试了一个列表逆向[[c“;” e“;” z“;” g“;” d“;” b“;” a“]，这给了我两个插入树。那真的让我感到困惑，以至于我不知道我的插入方法是对还是错。所以现在我有两个问题：
如果我的插入方法错误？
合并的左派树和插入的左派树是否具有相同的结构？我的意思是，这个结果给我一种错觉，就像它们在某种意义上是平等的一样。
整个代码
module type Comparable = sig
type t
val compare : t -> t -> int
end
module LeftistHeap(Elem:Comparable) = struct
exception Empty
exception Same_elem
type heap = E | T of int * Elem.t * heap * heap
let rank = function
| E -> 0
| T (r ,_ ,_ ,_ ) -> r
let makeT x a b =
if rank a >= rank b
then T(rank b + 1, x, a, b)
else T(rank a + 1, x, b, a)
let rec merge m n = match (m, n) with
| (h, E) -> h
| (E, h) -> h
| (T (_, x, a1, b1) as h1, (T (_, y, a2, b2) as h2)) ->
if (Elem.compare x y) < 0
then makeT x a1 (merge b1 h2)
else makeT y a2 (merge b2 h1)
let insert_merge x h = merge (T (1, x, E, E)) h
let rec insert x t =
try
match t with
| E -> T (1, x, E, E)
| T (_, y, left, right ) ->
match (Elem.compare x y) with
| n when n < 0 -> makeT x left (insert y right)
| 0 -> raise Same_elem
| _ -> makeT y left (insert x right)
with
Same_elem -> t
let rec creat_l_heap f = function
| [] -> E
| h::t -> (f h (creat_l_heap f t))
let create_merge l = creat_l_heap insert_merge l
let create_insert l = creat_l_heap insert l
end;;
module IntLeftTree = LeftistHeap(String);;
open IntLeftTree;;
let l = ["a";"b";"d";"g";"z";"e";"c"];;
let lh = create_merge `enter code here`l;;
let li = create_insert l;;
let h = ["c";"e";"z";"g";"d";"b";"a"];;
let hh = create_merge h;;
let hi = create_insert h;;
2015年10月16日更新
通过更精确地观察这两种实现，很容易发现区别在于合并基本树
T (1, x, E, E)或插入元素x我使用的图可以更清楚地表达。因此，我发现我的插入版本将始终使用更多的复杂性来完成他的工作，并且不会利用左派树的优势，或者即使在这种树结构恰好是“左派”的情况下，它也总是在更坏的情况下起作用。
如果我更改了一部分，则这两个代码将获得相同的结果。
let rec insert x t =
try
match t with
| E -> T (1, x, E, E)
| T (_, y, left, right ) ->
match (Elem.compare x y) with
| n when n < 0 -> makeT x E t
| 0 -> raise Same_elem
| _ -> makeT y left (insert x right)
with
Same_elem -> t
因此，对于我的第一个问题：我认为答案并不确切。它可以真正构建左派树，但总是在恶劣的情况下工作。
第二个问题是没有意义的（我不确定）。但是对于这种情况仍然很有趣。例如，即使合并版本的工作效率更高，但它也可以从列表构造树，而无需像我提到的那样插入顺序（[[a“;” b“;” d“;” g“;” z“; “ e”;“ c”]，[“ c”;“ e”;“ z”;“ g”;“ d”;“ b”;“ a”]，如果顺序不重要，对我来说认为它们是同一集合。）合并功能无法选择更好的解决方案。 （我认为[“ a”;“ b”;“ d”;“ g”;“ z”;“ e”;“ c”]的树结构比[“ c”;“ e”;“ z“;” g“;” d“;” b“;” a“]的）
所以现在我的问题是：
右下主干为Empty的树结构是好的结构吗？
如果是，我们是否可以始终按任何输入顺序构造它？
最佳答案
一棵树，每个右下脊骨都为空。这样一个简单的列表对于列表来说是一个更好的结构。运行时属性将与列表相同，这意味着例如插入将花费O(n)时间而不是所需的O(log n)时间。
对于一棵树，通常需要一棵平衡的树，一棵所有节点的子节点都理想地具有相同的大小。在您的代码中，每个节点都有一个rank，目标是使每个节点的左侧和右侧具有相同的等级。如果树中没有确切的2^n - 1条目，则不可能，并且必须允许树中存在一些不平衡。通常允许等级差为1或2。插入应将元素插入具有较小秩的一侧，并且删除必须重新平衡超过允许的秩差的任何节点。这样可以使树保持合理的平衡，从而确保保留所需的运行时属性。
检查您的教科书，根据情况允许在等级上有何不同。