I hope that someone else here would chime in on the issue raised in the
thread, about using a tree-structure that has multiple valid
configurations for the same set of unspent-TxOuts.  If you use any
binary tree, you must replay the entire history of insertions and
deletions in the correct order to get the tree structure and correct
root.  Along those lines, using something like a red-black tree, while
theoretically well-known, could be subject to implementation errors.
One implementation of a red-black tree may do the rebalancing
differently, and still work for it's intended purpose in the majority of
applications where it doesn't matter.  One app developer updates their
RB tree code which updated the RB-tree optimizations/rebalancing, and
now a significant portion of the network can't agree on the correct
root.  Not only would that be disruptive, it would be a disaster to
track down.

If we were to use a raw trie structure, then we'd have all the above
issues solved:  a trie has the same configuration no matter how elements
are inserted or deleted, and accesses to elements in the tree are
constant time -- O(1).  There is no such thing as an unbalanced trie.
But overall space-efficiency is an issue.

A PATRICIA tree/trie would be ideal, in my mind, as it also has a
completely deterministic structure, and is an order-of-magnitude more
space-efficient.  Insert, delete and query times are still O(1).
However, it is not a trivial implementation.  I have occasionally looked
for implementations, but not found any that were satisfactory.