高速バイナリ検索のための展開されたツリーとして展開されたツリー

Question

私はソートされたフラットリスト（展開されたリンクリストデータ構造）になるツリーデータ構造を持っています。ここで私は高速バイナリ検索を行いたいと思いました。各リスト要素は元のツリー構造からMID子要素である別の要素へのポインタを格納します。速い削除のために、各要素がその「親」を指すのも良いでしょう。

質問：

• これは、すでに指定されたデータ構造ですか？その「公式な」名前は何ですか？
• ソートされた挿入、削除、およびキーaka検索によるランダムアクセスの時間複雑度O（？）はどのくらいですか？

[編集]これは、このような構造の半グラフである：（JSON表記で書かれた）

このツリー：

{ 
     "abc": { 
     "a": 42, 
     "b": 43, 
     "c": 44 
     }, 
     "d": 45, 
     "e": { 
     "f": { 
      "g": 46, 
      "h": 47 
     } 
     } 
    } 

このリストに平坦化される。 （ " - > x"は、要素がインデックスxにある要素のアドレスを指していることを意味する） （各要素は元のツリーのキーと値があればそれを格納する）

[0] "abc": nil -> 2 
    [1] "a": 42 -> nil 
    [2] "b": 43 -> nil 
    [3] "c": 44 -> nil 
    [4] "d": 45 -> nil 
    [5] "e": nil -> 6 
    [6] "f": nil -> 7 
    [7] "g": 46 -> nil 
    [8] "h": 47 -> nil 

伝説：私が正しく理解していれば（あなたも前の要素にリンクしている場合は二重にリンクされたリスト）

[INDEX] "KEY": VALUE -> ADDRESS OF MID CHILD ELEMENT 

Answer 1

、あなたがlinked listを考えています。

挿入について、リンクされたリストはO（n）の検索時間とO（1）の挿入時間を持ち、木は検索時間とO（n）からO彼らのソート方法については、see for yourselfをお伝えします。

最後に、O（ログn）検索時間のツリーを使用している場合は、直接使用する方がよいでしょう。それ以外の場合は、ツリーをソートされたリンクリスト（たぶんO（n））。

また、ボーナスとして、ツリーの「中間」の子を読む科学用語は、事前注文とポストオーダートラバースとは対照的に、「インオーダートラバーサル」と呼ばれます。