Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: