Maintaing list order in binary tree

Question

Given a sequence of numbers, I want to insert numbers into a balanced binary tree, so when I traverse the tree, it returns me the sequence.

How can I build an insertion method that meets this requirement?

Remember that the tree must be balanced, so there is no absolutely trivial solution. I tried to do this with a modified version of the AVL tree, but I'm not sure if this might work.

I also want to be able to implement the delete operation. Delete should delete the item at the i-th position in the list.

Edit: Explanation:

I want to have: Insert (i, e), which inserts one element e directly in front of the i-th element in the sequence. Delete (i), which deletes the ith element of the sequence.

If I insert (0, 5), insert (0, 4), insert (0, 7), then my saved sequence is now 7, 4, 5, and traversing in the binary tree should give me 7, 4, 5.

If I delete (1), then traversing the binary tree in order should give me 7, 5. As you can see, the sequence order is maintained after removing the ith element of the sequence with i = 1 in this case (as I indexed my sequence from 0).

Answer 1

This can be done using the AVL tree.

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

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

node, node, //, O (log n). node , node + 1.

AVL , node node node.

O (log n), , / node .

, , , , , , [m, n] O (log n).

Answer 2

. / . , . , . , O (1), , .

: , Java

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 3

(, ), , . , , .

, , . , , , . , log_2 n .

Here is the C ++ code. Note that “end” refers to the index of the element located beyond the end of the current segment of the array.

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