Sequence of numbers on which various operations are performed presented as the AVL Tree

Question

So - I have a given sequence of numbers on which I have to perform a certain number of operations to insert and remove some of its elements. I also need a pointer that points to the currently used element.

It should look like this:

If I provide the program with a sequence of numbers 6 0 5 2 7 11 - the pointer is at the beginning (currently at the number 6). If this number is even, I have to remove the number in the next position - in this case - number 0 and then move the pointer by (value of deleted element). So the sequence would look like this: 6 5 2 7 11 and pointer would still be at number 6. It's also important that the sequence should work like a loop, so next element after the last one is first element of the sequence.

The second case is when number under pointer is odd. If it happens, I have to add an element with the value: (value of number under pointer) - 1 and move the pointer by the value currently under it(7 in this case). So in the sequence 7 2 6 and pointer on element 7 - it would look like this: 7 6 2 6 and pointer would be on last 6 in the sequence.

So, using the previous example - the supplied sequence of numbers is 6 0 5 2 7 11 and the pointer is on number 6.

6 0 5 2 7 11 - pointer on number 6.

6 5 2 7 11 - 6 is even so I remove the next element, pointer remains at 6 because the value of the deleted number is 0.

6 2 7 11 - Same situation but this time I move the pointer 5 elements to the right, so it is now on the number 2.

6 2 11 - 2 is also even, so I remove 7 and move pointer 7 elements to the right.

6 2 11 10 - 11 is odd, so I add (11 - 1) as the next element of the sequence and move pointer by 11 elements.

After performing 4 operations of adding or deleting elements, the sequence of numbers looks like this: 6 2 11 10.

My problem is how to implement this algorithm using an AVL tree, because I want its time complexity to be xlogn, where x is the number of insertion or deletion operations that need to be performed

My first thought was to simply store the index of each node, which would allow me to quickly search for subsequent elements of the tree (e.g. if I know that I need to move the pointer in the sequence by 5 elements, I could add its current value to 5 and search the tree for the element with index x + 5) and then perform some action, e.g. add the number 10 as the next element. The problem is that if the number 10 will now have the index x + 5 + 1, then I have to change the indexes for all the next elements in the sequence, and it seems to me that this will not achieve the time complexity of xlogn.

So my question is how can I solve this problem?

Of course, if something is unclear, I will try to explain it in a different, simpler way.

Answer 1

An AVL tree is a fairly bad fit for this. What you really want is a tree that knows how many children it has. That is you want a class for a node in your tree which looks something like this.

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

    ...
}

Let's make a simplifying choice and cheat - nodes are actually interior nodes or leaves. We only look at value if leftSize and rightSize are 0.

If this is an interior node, its size will be leftSize + rightSize. Otherwise it is a leaf with size 1.

If we don't care about balanced trees, this is already enough. We can store as many values as we like, and find them by position something like this.

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;
    }
}

As long as we don't worry about rebalancing, inserts and deletes are easy to code. Just walk the tree, changing sizes, and then insert/delete a leaf.

Worrying about rebalancing is always the hard part. But we can solve that as follows. We need to rebalance when 2*leftSize + 1 < rightSize or 2*rightSize + 1 < leftSize. To rebalance, we simply construct a perfectly balanced tree from an in order traversal in time O(size). Yes, this is expensive. But since it takes O(size) operations after the creation of a node to have to rebalance it, the amortized cost per level per operation is at most O(1). There are O(log(n)) levels, so the amortized cost is at most O(log(n)).

With this, to access a value by index you just take the index modulo the size, and then do a find to find it. Or insert or delete.

And now that you can access things by index, your program is easy to write.

---

More notes.

Position really is the position of the node in the data structure.

To build the tree, I would recommend having constructors like this:

TreeNode (int startValue) {
    value = startValue;
}

TreeNode (int size, Iterator<int> valueIter) {
    // Should really throw an exception if size < 1.
    // I'll leave that to you. Definitely do it if you get an endless loop.
    if (size == 1) {
        value = valueIter.next();
    }
    else {
        leftSize = size / 2;
        left = TreeNode(leftSize, valueIter);
        rightSize = size - leftSize;
        right = TreeNode(rightSize, valueIter);
    }
}

And now you can build a balanced tree from anything that you can make an Iterator from. Build your own TreeNodeIterator class and you can now make rebalancing work as follows.

public void rebalance () {
    TreeNodeIterator iter = TreeNodeIterator(this);
    TreeNode copy = TreeNode(self.size(), iter);

    value = copy.value;
    leftSize = copy.leftSize;
    rightSize = copy.rightSize;
    left = copy.left;
    right = copy.right;
}