3

最近，我在阅读《Purely-functional-data-structures》一书时，来到 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 tree。这真的让我很困惑，以至于我不知道我的插入方法是对还是错。所以现在我有两个问题：

  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. 每个亚右脊为 Empty 的树形结构是好结构吗？
  2. 如果是，我们可以总是以任何输入顺序构造它吗？
4

1 回答 1

0

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

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

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

于 2018-04-16T14:24:52.827 回答