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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

回答：

如果我理解正确的话，你想一个linked list（或双向链表，如果你还链接到以前的元素）。

关于插入，链接列表的搜索时间为O（n），插入时间为O（1），树的搜索时间和访问时间范围从O（n）到O（log n），具体取决于关于他们如何排序，我会让你see for yourself。最后，如果你使用的是一个O（log n）搜索时间的树，你最好直接使用它，否则它取决于将树变成排序链接需要多长时间列表（可能是O（n））。另外，作为奖励，阅读树的“中”孩子的科学术语被称为“顺序遍历”，而不是预顺序和后顺序遍历。

以上是 扁平树作为展开链接列表快速二进制搜索 的全部内容， 来源链接： utcz.com/qa/265922.html

回到顶部