Finger Trees

http://andrew.gibiansky.com/blog/haskell/finger-trees/

by PieSquared • 12 years ago

54 13 12 years ago

andrew.gibiansky.com

wrl2• 12 years ago

So, if I'm understanding this right, finger trees are just 2-3 trees with an extra array of 8 things per level (four for prefix, four for suffix). Does this really have a benefit over just using a 2-3 tree?

gjm11• 12 years ago

You get amortized-constant-time additions and deletions at both "ends", which is a pretty big deal for some use cases. And log-time concatenation, which I don't think 2-3 trees give you. And it's all done purely functionally, which means you get persistence if you want it (i.e., you can keep around old versions of the data structure and the only cost you pay is the memory).

wrl2• 12 years ago

The log-time concatenation may be the real win. Still though, why 4? Why not 2, or 8? Is this covered in some of the research?

jbapple3• 12 years ago

2-3 trees actually do give you log-time concatenation; most species of balanced trees do, including red-black, AVL, splay (amortized, of course), skip lists, and treaps.

bkirwi2• 12 years ago

I don't think that's quite right -- have a close look at the translation of the example finger tree to code. (Grep for "The translation of this tree".)

The basic intuition is that the far left and right of the original tree have been 'lifted up' to just under the root. This means access to the tips is constant time instead of O(log(n)), which has obvious benefits for some access patterns. The really neat thing about this data structure, though, is all the other neat properties these trees have: you can implement random-access arrays and priority queues and a bunch of other patterns quite efficiently, just by tweaking a parameter or two.

bkirwi2• 12 years ago

This is a really nice use of the IHaskell Notebook[0] -- nice to see it in the wild.

[0] https://github.com/gibiansky/IHaskell

Fede_V• 12 years ago

Gibiansky's blog is chuck full of incredibly good stuff. He updates sporadically but it's totally worth a read.

Finger Trees

Related Stories