执行各种操作的数字序列呈现为 AVL 树

Question

所以 - 我有一个给定的数字序列，我必须对其执行一定数量的操作来插入和删除其一些元素。我还需要一个指向当前使用的元素的指针。

它应该看起来像这样：

如果我向程序提供数字序列 6 0 5 2 7 11 - 指针位于开头（当前位于数字 6）。如果这个数字是偶，我必须删除下一个位置的数字 - 在本例中 - 数字 0，然后将指针移动（已删除元素的值）。因此序列将如下所示： 6 5 2 7 11 并且指针仍位于数字 6。序列应像循环一样工作也很重要，因此最后一个元素之后的下一个元素是序列的第一个元素。

第二种情况是指针下的数字为奇数。如果发生这种情况，我必须添加一个值为：(指针下数字的值) - 1 的元素，并将指针移动当前位于其下的值（在本例中为 7）。因此，在序列 7 2 6 中，指针位于元素 7 上 - 看起来像这样： 7 6 2 6 ，指针将位于序列中的最后 6 个上。

因此，使用前面的示例 - 提供的数字序列是 6 0 5 2 7 11 并且指针位于数字 6 上。

6 0 5 2 7 11 - 指针位于数字 6 上。

6 5 2 7 11 - 6 是偶数，所以我删除下一个元素，pointer 仍为 6，因为删除的数字的值为 0。

6 2 7 11 - 同样的情况，但这次我将指针向右移动 5 个元素，所以它现在位于数字 2 上。

6 2 11 - 2 也是偶数，所以我删除 7 并将 pointer 7 个元素向右移动。

6 2 11 10 - 11 是奇数，因此我添加 (11 - 1) 作为序列的下一个元素，并将 pointer 移动 11 个元素。

执行4次添加或删除元素操作后，数字序列如下：6 2 11 10。

我的问题是如何使用AVL树实现这个算法，因为我希望它的时间复杂度为xlogn，其中x是需要执行的插入或删除操作的数量

我的第一个想法是简单地存储每个节点的索引，这将允许我快速搜索树的后续元素（例如，如果我知道我需要将序列中的指针移动 5 个元素，我可以添加其当前值设置为 5 并在树中搜索索引为 x + 5 的元素），然后执行一些操作，例如添加数字 10 作为下一个元素。问题是，如果数字 10 现在有索引 x + 5 + 1，那么我必须更改序列中所有下一个元素的索引，在我看来，这不会达到 xlogn 的时间复杂度.

所以我的问题是如何解决这个问题？

当然，如果有什么不清楚的地方，我会尝试用不同的、更简单的方式来解释。

Answer 1

AVL 树不太适合这种情况。你真正想要的是一棵知道它有多少个孩子的树。也就是说，您想要为树中的节点提供一个类，如下所示。

public class TreeNode {
    int value;
    int leftSize;
    int rightSize;
    TreeNode left;
    TreeNode right;

    ...
}

让我们做一个简化的选择和作弊——节点实际上是内部节点或叶子。如果

value

和

leftSize

为 0，我们只查看

rightSize

。

如果这是一个内部节点，它的大小将为

leftSize + rightSize

。否则它是一片大小为 1 的叶子。

如果我们不关心平衡树，这已经足够了。我们可以存储任意数量的值，并通过位置找到它们，就像这样。

public int find (int pos) {
    // We assume that 0 <= pos < tree size
    if (pos < leftSize) {
        return left.find(pos);
    }
    else if (pos < leftSize + rightSize) {
        return right.find(pos - leftSize);
    }
    else {
        // Should only happen when pos is 0 and this is a leaf.
        return value;
    }
}

只要我们不担心重新平衡，插入和删除就很容易编写代码。只需走动树，改变大小，然后插入/删除一片叶子。

担心重新平衡始终是最困难的部分。但我们可以按如下方式解决这个问题。当

2*leftSize + 1 < rightSize

或

2*rightSize + 1 < leftSize

时，我们需要重新平衡。为了重新平衡，我们只需从时间上的有序遍历构建一个完美平衡的树

O(size)

。是的，这很贵。但由于创建节点后需要

O(size)

次操作才能重新平衡节点，因此每个操作每级的摊销成本最多为

O(1)

。有

O(log(n))

个级别，因此摊余成本最多为

O(log(n))

。

有了这个，要通过索引访问

value

，只需对索引的大小取模，然后执行

find

即可找到它。或者插入或删除。

现在您可以通过索引访问内容，您的程序很容易编写。