data-structures - Leftist ヒープ 2 バージョン作成実装

Question

最近、Leftist_tree の「Exercise 3.2 マージの呼び出しではなく直接挿入を定義する」に来たときに、Purely-functional-data-structures という本を読んでいます。

 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"]このツリーを作成するための入力としてリストを使用しました。そして、2 つの結果は異なります。マージ メソッドの場合、次のようなツリーを取得しました。

実装した挿入メソッドは、次のようなツリーを提供します。

「挿入」バージョンを設計するために「マージ」の実装に従っていますが、2 つの方法の間にはいくつかの詳細があると思います。しかし、その後、逆のリスト ["c";"e";"z";"g";"d";"b";"a"] を試してみると、2 つのleftist-tree-by-insert tree が得られました。それは私をとても混乱させたので、挿入方法が間違っているか正しいかわかりません。だから今、私は2つの質問があります：

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月更新

2 つの実装をより正確に観察すると、違いがベース ツリーのマージか、より明確に表現できるグラフを使用T (1, x, E, E)した要素の挿入にあることが簡単にわかります。x

そのため、このツリー構造はまさに「左派」であるにもかかわらず、私の挿入バージョンは常により複雑な作業を使用して左派ツリーの利点を利用しないか、常に悪い状況で機能することがわかりました。

少し変更すると、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 E t
    | 0 -> raise Same_elem
    | _ -> makeT y left (insert x right)
with
  Same_elem -> t

私の最初の質問ですが、答えは正確ではないと思います。それは本当に左派のツリーを構築することができますが、常に悪い状況で機能します。

2番目の質問は少し無意味です（よくわかりません）。しかし、それでもこの条件は興味深いものです。たとえば、マージ バージョンはより効率的に機能しますが、前述のように挿入順序を必要とせずにリストからツリーを構築します (["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. それぞれの副右背骨が空のツリー構造は良い構造ですか?
2. はいの場合、常に任意の入力順序で構築できますか?