> 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 ephe

> 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.