<p>If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that location.</p>

CC BY-SA 3.0
2014-06-12T22:03:17.420Z
Ah, thanks.  I was thinking trees with no parent link, but I suppose that I can maintain a separate linked list of pointers to the the right spine.
David C
CC BY-SA 3.0
2014-06-13T00:12:37.873Z
Or you can keep only reversed pointers (child points to parent) during the  creation of the tree, then reverse them when you're done.
jbapple
CC BY-SA 3.0
2014-06-12T00:57:04.367Z
2014-06-12T00:57:04.367Z
jbapple
<p>Given an ordered stream of <em>n</em> items (<em>n</em> unknown in advance), it is well-known how to construct a red-black tree from them in O(<em>n</em>)-time.  More specifically this is possible using only O(log <em>n</em>) additional storage, and only O(log <em>n</em>)-time after then <em>end-of-stream</em> is discovered.  The technique involves pennants and the 1-2 binary representation of <em>n</em>.</p>

<p>The technique needs to be modified for AVL trees, and I haven't seen referneces to an on-line algorithm for creating AVL trees.  Does anyone know of such a published algorithm? </p>

CC BY-SA 3.0
2014-06-12T00:51:52.207Z
Do you have a citation for the claim about red-black trees? Do the items arrive in sorted order?
jbapple
<ds.algorithms><ds.data-structures><online-algorithms><binary-trees>
Are there published algorithms for on-line creation of AVL trees from ordered streams?
David C
# Are there published algorithms for on-line creation of AVL trees from ordered streams?

(Asked by: username_0 on 2014-06-12)

Given an ordered stream of *n* items (*n* unknown in advance), it is well-known how to construct a red-black tree from them in O(*n*)-time. More specifically this is possible using only O(log *n*) additional storage, and only O(log *n*)-time after then *end-of-stream* is discovered. The technique involves pennants and the 1-2 binary representation of *n*.

The technique needs to be modified for AVL trees, and I haven't seen referneces to an on-line algorithm for creating AVL trees. Does anyone know of such a published algorithm?

**Tags:** ds.algorithms, ds.data-structures, online-algorithms, binary-trees
> **Comments:**
> **username_1**: Do you have a citation for the claim about red-black trees? Do the items arrive in sorted order?  

---

## 1 answers

### Answer by username_1 on 2014-06-12. Score: 1

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that location.

> **Comments:**
> **username_0**: Ah, thanks.  I was thinking trees with no parent link, but I suppose that I can maintain a separate linked list of pointers to the the right spine.  
> **username_1**: Or you can keep only reversed pointers (child points to parent) during the  creation of the tree, then reverse them when you're done.  

---

