3 ms·
I've never been very good at data structures, but the increasing size of trees makes it sound like finger trees: http://en.wikipedia.org/wiki/Finger_tree http:/
by gwern 16y ago
I've never been very good at data structures, but the increasing size of trees makes it sound like finger trees: http://en.wikipedia.org/wiki/Finger_tree http://en.wikipedia.org/wiki/Finger_tree
- daniel-cussen 16y agoThanks for the link. While they both use trees they're not the same thing.
- pjscott 16y agoFinger trees are even more impressive than this (very clever) data structure. A sequence based on finger trees supports: * O(lg n) lookup, split, concatenate, random insert/delete * amortized O(1) push and pop at either end of the sequence * Caching the value of a monoid reduction of each subsequence. Surprisingly useful. Trellises are easier to understand, though.