扁平树作为展开链接列表快速二进制搜索

我有一个树型数据结构，我变成一个排序的扁平列表（展开链接列表数据结构）。现在我想做一个快速的二分搜索，我想到的想法是：每个列表元素存储一个指向另一个元素的指针，该元素是来自原始树结构的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

扁平树作为展开链接列表快速二进制搜索

回答

相关问题