扁平樹作爲展開鏈接列表快速二進制搜索

我有一個樹型數據結構，我變成一個排序的扁平列表（展開鏈接列表數據結構）。現在我想做一個快速的二分搜索，我想到的想法是：每個列表元素存儲一個指向另一個元素的指針，該元素是來自原始樹結構的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

來源

2017-09-27 kitomer

如果我理解正確的話，你想一個linked list（或雙向鏈表，如果你還鏈接到以前的元素）。

關於插入，鏈接列表的搜索時間爲O（n），插入時間爲O（1），樹的搜索時間和訪問時間範圍從O（n）到O（log n），具體取決於關於他們如何排序，我會讓你see for yourself。最後，如果你使用的是一個O（log n）搜索時間的樹，你最好直接使用它，否則它取決於將樹變成排序鏈接需要多長時間列表（可能是O（n））。另外，作爲獎勵，閱讀樹的「中」孩子的科學術語被稱爲「順序遍歷」，而不是預順序和後順序遍歷。

來源

2017-09-27 08:18:00 anto418

我知道鏈表中的每個元素都包含一個指向下一個元素的指針。我所擁有的是一個鏈表（相當於一個展開鏈表，但在這裏看起來並不相關），其中一個元素指向其子元素的中間（假設元素以前是具有n個子節點的樹結構的一部分）。這個結構與正常的鏈表不同。這有一個名字嗎？ – kitomer

至於爲什麼我將原始樹結構扁平化：實際上，我甚至沒有樹，但將數據保存在展開的鏈接列表中。我在我的問題中引入了樹來說明數據的實際語義結構。 – kitomer

@kitomer我不確定我真的得到了你在說什麼結構（特別是你如何定義「子元素的中間」）。你能舉一個例子嗎？圖，類/結構定義，「添加」方法？ – anto418

扁平樹作爲展開鏈接列表快速二進制搜索

回答

相關問題