Maintaing list order in binary tree

Question

Given a sequence of numbers, I want to insert the numbers into a balanced binary tree such that when I do a inorder traversal on the tree, it gives me the sequence back.

How can I construct the insert method corresponding to this requirement?

Remember that the tree must be balanced, so there isn't a completely trivial solution. I was trying to do this with a modified version of an AVL tree, but I'm not sure if this can work out.

I also wish to be able to implement a delete operation. Delete should delete the item at the ith position in the list.

Edit: clarification:

I want to have: Insert(i, e), which inserts a single element e right before the ith element in the sequence. Delete(i), which deletes the ith element of the sequence.

If I do insert(0, 5), insert(0, 4), insert(0, 7), then my stored sequence is now 7, 4, 5 and inorder traversal on the binary tree should give me 7, 4, 5.

If I do delete(1), then inorder traversal on the binary tree should give me 7, 5. As you can see, the sequence order is maintained after deleting the ith sequence element with i = 1 in this case (as I've indexed my sequence from 0).

Answer 1

Keep a linked list in the tree. You already have pointers/references to the nodes thanks to the tree. When you insert into the tree, also insert at the end of the linked list. When you remove from the tree, remove from the linked list. Because you have the references, they're all O(1) operations, and you can iterate through in insertion order if you so choose.

Edit: to clarify Bart's concern, here's a Java implementation

class LinkedTreeNode<E> {
   E data;
   LinkedTreeNode<E> parent;
   LinkedTreeNode<E> left;
   LinkedTreeNode<E> right;
   LinkedTreeNode<E> insertNext;
   LinkedTreeNode<E> insertPrev;
}

class LinkedTree<E> {
    LinkedTreeNode<E> root;
    LinkedTreeNode<E> insertHead;
    LinkedTreeNode<E> insertTail;

    // skip some stuff
    void add(E e) {
        LinkedTreeNode<E> node = new LinkedTreeNode<E>(e);

        // perform the tree insert using whatever method you like

        // update the list
        node.insertNext = insertTail;
        node.insertPrev = insertTail.insertPrev.insertPrev;
        node.insertPrev.insertNext = node;
        insertTail.insertPrev = node;
    }

    E remove(E e) {
        LinkedTreeNode<E> rem = // whatever method to remove the node
        rem.insertNext.insertPrev = rem.insertPrev;
        rem.insertPrev.insertNext = rem.insertNext;
        return rem.data;
    }
} 

Answer 2

If you have random access to the contents of the sequence (e.g. you have an array), then you can simply build the tree directly, so that pre-order traversal provides the sequence you want. It can actually be done without random access, but less efficiently, since linear scans may be required to find the midpoint of the sequence.

The key observation here is that the first value in the sequence goes in the root of the tree, then the remainder of the sequence can be divided into halves. The first half will go into the subtree rooted at the left child and the second half will go into the subtree rooted at the right child. Because you are dividing the remaining list in half at each step, the resulting tree will have log_2 n levels and will be balanced.

Here's some C++ code. Note that "end" refers to the index of the element just past the end of the current array segment.

struct Node {
    Node(int v) : value(v), l(0), r(0) {}

    int value;
    Node* l;
    Node* r;
};

Node* vector_to_tree(int begin, int end, int array[]) {
    if (begin == end)
        return NULL;

    Node* root = new Node(array[begin++]);
    int mid = (begin + end) / 2;
    root->l = vector_to_tree(begin, mid, array);
    root->r = vector_to_tree(mid,   end, array);

    return root;
}

void preorder_traverse(Node* root) {
    if (!root)
        return;

    std::cout << root->value << std::endl;
    traverse(root->l);
    traverse(root->r);
}

Answer 3

This can be done with an AVL tree.

Add items to the AVL tree by adding to the rightmost node of the tree.

AVL balancing does not affect the inorder traversal property due to the nature of rotations.

Storing the size of the tree at each node, and maintaining these values for each node affected during inserts/deletes/balances can be done in O(log n) time. Storing the size of the tree at each node permits searching for an item by rank in the sequence, since the rank of an item in a tree is known by a node's left child's size + 1.

Deletion from the AVL tree can be accomplished by replacing a removed node with the leftmost node of the node's right subtree.

Insert and delete operations are then done in O(log n) time, since the tree is always balanced, and size updates on the nodes are done along a path from inserted/deleted node to root.

Since there is no backing data structure other than a binary tree, other operations that benefit from a tree can be done, such as finding the sum of an [m, n] range of elements in the sequence in O(log n) time.