data-structures - 左堆二版创建实现

Question

最近在看《纯函数式数据结构》这本书当我来到 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"]，它给了我两个 leftist-tree-by-insert树。这真的让我很困惑，我不知道我的插入方法是错误的还是正确的。所以现在我有两个问题:

1. 如果我的插入方法有误？
2. leftist-tree-by-merge 和leftist-tree-by-insert 是相同的结构吗？我的意思是这个结果给我一种错觉，好像他们在某种意义上是平等的。

全部代码

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

---

<强>16。 2015 年 10 月更新

通过更精确地观察这两个实现，很容易发现不同之处在于合并一个基础树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"])

所以现在我的问题是:

1. 每个sub-right spine都是Empty的树结构是不是一个好的结构？
2. 如果是，我们能否始终以任何输入顺序构建它？

Answer 1

每个子右脊柱为空的树只是一个列表。因此，一个简单的列表是一个更好的列表结构。运行时属性将与列表相同，这意味着例如插入将花费 O(n) 时间而不是所需的 O(log n) 时间。

对于一棵树，您通常需要一棵平衡树，理想情况下，一个节点的所有子节点大小都相同。在您的代码中，每个节点都有一个 rank 并且目标是每个节点的左侧和右侧具有相同的等级。如果您在树中没有完全 2^n - 1 条目，这是不可能的，您必须允许树中存在一些不平衡。通常允许 1 或 2 的等级差异。插入应该在等级较小的一侧插入元素，移除必须重新平衡任何超过允许等级差异的节点。这使树保持合理平衡，确保保留所需的运行时属性。

检查你的教科书在你的情况下允许的排名差异。