1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you have a citation for the claim about red-black trees? Do the items arrive in sorted order? $\endgroup$ – jbapple Jun 12 '14 at 0:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David C Jun 12 '14 at 22:03
  • 1
    $\begingroup$ Or you can keep only reversed pointers (child points to parent) during the creation of the tree, then reverse them when you're done. $\endgroup$ – jbapple Jun 13 '14 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.