3
$\begingroup$

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.

To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.

In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.

$\endgroup$
4
$\begingroup$

From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?"

You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is replicate, which takes a value $v$ and size $n$, then creates a finger tree of size $n$ containing $n$ copies of $v$. The real work of replicate is done in applicativeTree, which has individual cases for $n \leq 8$ and recurses for larger $n$.

$\endgroup$
  • $\begingroup$ Ah, that was silly of me! I should've gone straight to the source! You don't really need to know the shape of the tree to do it! I also should've seen the obvious recursion involved in such an algorithm, since every deep tree is just another tree for which similar rules apply. As it happens, that exact algorithm can't work for me, but it was simple to change it so it would. $\endgroup$ – GregRos Apr 6 '15 at 20:31

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.