4

假设我们最初得到一组 n 个数字。我们需要构建一个支持 Search()、Predecessor() 和 Deletion() 查询的数据结构。

Search 和 Predecessor 应该花费最坏情况 O(log processing n) 时间。删除应该花费平摊的 O(log n) 时间。允许的提前时间为 O(n)。我们最初有 O(n) 空间。但我希望在任何阶段，如果它们是结构中的 m 个数字，则使用的空间应该是 O(m)

这个问题可以使用 RBT 轻松解决，但我想要一个仅使用数组的数据结构。我不想使用数组来实现 RBT，数据结构不应该使用任何受树启发的算法。谁能想到一种这样的数据结构？

4

1 回答 1

0

我可以建议某种树结构，这比 RBT 容易。为了简化它的描述，让其中的元素数量为2^k.

第一级只是数字。第二个级别 a 有2^(k-1)数字，就像在二叉树中一样。下一级 a 有2^(k-2)数字，依此类推，直到我们只有一个数字。所以我们有一个带有节点的二叉树2^(k+1)，并且父节点将包含最多的子节点值。要建造这棵树，我们将是O(N)时间。树将消费O(n)空间，一级消费者n，二级n/2，三级n/4......等等，所以总空间将是n + n/2 + n/4 + ... = 2n = O(n)。例如，对于数字 1、2、4、6、8、9、12、14，我们将有以下树：

 1  2  4  7  8  9 12  14 

   2    7     9     14 

      7          14

            14

要删除元素，我们需要使用二进制搜索找到它并在列表中将它们标记为空。更新树，如果两个子节点都为 NULL，则将 NULL 放入节点。这将需要 k 次操作（树高）或 O(log(N))。例如我们删除 12。

 1  2  4  7  8  9 NULL(12)  14 

   2    7     9     14 

      7          14

            14

现在删除 7。

 1  2  4  NUll(7)  8  9 NULL(12)  14 

   2    4            9     14 

      4                 14

            14

现在我们应该在 O(log(N)) 中搜索或前任。通过二分搜索在第一级找到我们的元素或其前身。如果它不为 NULL，我们将得到答案。如果 NULL 升级，我们在这里有三个变体：

  1. 节点有NULL值，上一级
  2. 节点的左孩子有一个非空值。它小于请求的数字（由于树结构），这就是答案。
  3. 节点的值大于然后请求的数字，向上。
于 2015-11-11T14:41:16.693 回答