为init、insert、delete、median创建一个数据库
Create a database for init,insert,delete,median
我需要创建一个在这个时间复杂度下工作的数据库：
初始化 O(1)
插入 O(logn)
删除O(logn)
求中位数 O(1)
我正在努力寻找 O(1) 中的中位数。
我创建了一个空的 AVL 树，以及 1., 2. ,3.就像具有所需时间复杂度的魅力一样工作。我想着每次对树输入时都持有一个指向中位数的指针，但是当我删除一个节点时，如何在树中找到logn中的中位数？因为我相信我做不到。它需要大约 O(n) 的时间复杂度。这意味着 3. 在更新指针以找到新的中位数后将无法使用 O(logn) 复杂度。
有什么想法吗？
此问题有多种解决方案，具体取决于您已有的解决方案：
Order Statistics tree，它是二叉搜索树的变体，允许您通过顺序统计快速（对数时间）访问元素。在您的例子中，您正在寻找第 ceil(n/2) 个元素。
虽然这意味着您会在 O(logn) 中找到中位数，但您可以在每个 insertion/deletion 之后轻松缓存它，并且它不会改变原始操作的复杂性 - 它将保持不变 O(logn).
另一种（可能更简单的）方法是使用以下观察：
每insertion/deletion个非空集后，中位数可以做三个选项之一：
一个。保持相同的元素。示例：1,2,3 -> 1,2,3,4 - 中位数仍然是 2，
b。向右移动一个元素。示例：1,2,3,4 -> 1,2,3,4,5 - 中位数从 2 更改为 3
c。向左移动一个元素。示例：1,2,3,4,5 -> 1,2,3,4（与之前相同，相反）。
假设您可以在对数时间内找到“上一个”和“下一个”元素，则只需很少的额外工作即可轻松维护指向中位数的指针。
我需要创建一个在这个时间复杂度下工作的数据库：
初始化 O(1)
插入 O(logn)
删除O(logn)
求中位数 O(1)
我正在努力寻找 O(1) 中的中位数。
我创建了一个空的 AVL 树，以及 1., 2. ,3.就像具有所需时间复杂度的魅力一样工作。我想着每次对树输入时都持有一个指向中位数的指针，但是当我删除一个节点时，如何在树中找到logn中的中位数？因为我相信我做不到。它需要大约 O(n) 的时间复杂度。这意味着 3. 在更新指针以找到新的中位数后将无法使用 O(logn) 复杂度。
有什么想法吗？
此问题有多种解决方案，具体取决于您已有的解决方案：
Order Statistics tree，它是二叉搜索树的变体，允许您通过顺序统计快速（对数时间）访问元素。在您的例子中，您正在寻找第
ceil(n/2)个元素。
虽然这意味着您会在O(logn)中找到中位数，但您可以在每个 insertion/deletion 之后轻松缓存它，并且它不会改变原始操作的复杂性 - 它将保持不变O(logn).另一种（可能更简单的）方法是使用以下观察：
每insertion/deletion个非空集后，中位数可以做三个选项之一：
一个。保持相同的元素。示例：1,2,3 -> 1,2,3,4- 中位数仍然是 2，
b。向右移动一个元素。示例：1,2,3,4 -> 1,2,3,4,5- 中位数从 2 更改为 3
c。向左移动一个元素。示例：1,2,3,4,5 -> 1,2,3,4（与之前相同，相反）。
假设您可以在对数时间内找到“上一个”和“下一个”元素，则只需很少的额外工作即可轻松维护指向中位数的指针。