扁平化树作为展开链表用于快速二分查找

Question

我有一个树数据结构，我把它变成一个排序的平面列表（一个展开的链表数据结构）。现在我想做一个快速的二进制搜索，我想到的想法是：每个列表元素都存储一个指向另一个元素的指针，该元素是原始树结构中的 MID 子元素。为了快速删除，每个元素也可以指向其 "parent"。

问题：

这已经是命名数据结构了吗？它的 "official" 名称是什么？
按键或搜索进行排序插入、删除和随机访问的时间复杂度 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(log n)根据它们的排序方式，我会让你 see for yourself.

最后，如果你使用的是搜索时间为 O(log n) 的树，你最好直接使用它，否则这取决于将你的树变成排序的需要多长时间链表（可能是 O(n)）。

此外，作为奖励，读取树的 "mid" 子树的科学术语称为 "in-order traversal"，与预序和 post 序遍历相反。

扁平化树作为展开链表用于快速二分查找

Flattened Tree as an Unrolled Linked List for fast Binary Search

tree

linked-list

binary-search