3 ms·
How are these better than balanced binary trees that keep subtree size in the node?
by jemfinch 16y ago
How are these better than balanced binary trees that keep subtree size in the node?
- daniel-cussen 16y agoPredictable structure and smaller nodes. And most of the other advantages linked lists have over binary trees, with some of those advantages being slower.
- jemfinch 16y agoIf I'm using both as a abstract data types, does predictable structure really help me at all?
- daniel-cussen 16y agoIf you're using it for code (the way Lisp uses linked lists) you know when one function ends and a nested one begins. I'd like to point out, however, that this is in theory, as I haven't seen this data structure doing anything other than moving data around.
- jbapple 16y ago> How are these better than balanced binary trees that keep subtree size in the node? I suspect that cons will be )(1) amortized (when the trellis is used ephemerally), which is not true of your usual balanced binary trees. There are many data structures that offer O(1) (amortized or worst-case) modification near the front, and several of them really are just balanced trees but with the pointers down the left spine reversed. In fact, this is a key idea behind Hinze & Patterson's FingerTress, mentioned elsewhere in this thread.