Keeping a binary tree balanced when elements are insert in order

Question

I was wondering if there is a suitable algorithm for maintaining the balance of a binary tree, when it is known that elements are always inserted in order.

One option for this would be to use the standard method of creating a balanced tree from a sorted array or linked list, as discussed in this question, and also this other question. However, I would like a method where a few elements can be inserted into the tree, lookups then performed on it, and other elements then added later, without having to decompose the tree to a list and re-make the whole thing.

Another option would be to use one of the many self-balancing tree implementations, AVL, AA, Red-Black, etc. etc. However, all of these impose some sort of overhead in the process of insertion, and I was wondering if there may be a way to avoid this given the constraint that elements are always inserted in increasing order.

So, for clarity, I would like know if there is a method by which I can maintain a balanced binary tree, such that I can insert an arbitrary new element into it at any point and keep the balance of the tree, providing that the new element is greater in the ordering of the tree than all elements already present in the tree.

As an example, suppose I had the following tree:

       4
      / \
     /   \
    2     6
   / \   / \
  1   3 5   7

Is there a simple way to maintain the balance when inserting a new element, if I know that the element will be larger than 7?

Solution 1

If you're really interested in doing it using a BST (which I think is not the best option, as you can read in my other answer), you could do it like this:

Have normal BST. That means lookups are O(log N), if we manage to keep the depth during insertions.

When doing an insertion (assuming we have an element larger than all previous ones), you walk from the root to the right-most element. When you encounter a node whose subtree is a perfect binary tree (all inner nodes have 2 children and all leaves are at the same depth), you insert the new node as a parent of this node.

If you reach the right-most node in the tree and you didn't apply the previous rule, that means it has a left child, but it doesn't have a right one. So, the new node becomes the right child of the current node.

For example, in the first tree below, the subtree of 4 is not perfect, but the subtree of 5 is (a tree with just one node is perfect by the definition). So, we add 6 as a parent of 5, which means 4 is parent of 6 now and 5 is the left child of 6.

If we try to add another node then, the subtree of 4 is still not perfect, and neither is the one of 6. And 6 is the right-most node, so we add 7 as the right child of 6.

     4             4             4
    / \           / \           / \
   /   \         /   \         /   \
  2     5 -->   2     6 -->   2     6
 / \           / \   /       / \   / \
1   3         1   3 5       1   3 5   7

If we use this algorithm, the subtree of the left child of the root will always be perfect and the subtree of the right child will never have bigger height than that of the left one. Because of that, the height of the whole tree will always be O(log N), and so will be the lookup time. The insertion will take O(log N) time too.

When compared with self-balancing BSTs, the time complexities are the same. But this algorithm should be easier to implement and might be actually faster than them.

When compared with the array-based solution from my other answer, the time complexity of lookup is the same, but this BST has worse insertion time.

Solution 2

For the requirement you describe, you don't need a tree at all. A sorted dynamic array is all you need.

When inserting, always insert at the end (O(1) amortized).

When searching, use normal binary search (O(log N)).

This assumes you don't need any other operations, or that you don't mind they will be O(N).

Comments

[Admin]

thank you very much for the answer, you are quite right that a tree is not neccessary for a general sorted set kindof algorithm in which elements are received in sorted order. However, I was more interested (out of curiosity) whether there was a way to do this with ordinary binary trees. Thanks again for the answer.

[Admin]

Thank you very much for the answer, you are right that a skip list, or as svick suggested, a dynamic array, would be well suited for generally keeping track of a set of elements which arrive in an a priori known order, however, I was more interested out of curiosity whether there is a way to do so with a binary tree.