As others have mentioned, a self-balancing binary search tree would solve the only real technical issue here. Red-black trees would work fine, or their generalized parent structure the 2-3-4 tree (B+tree of order 4), which would provide a conceptually cleaner implementation and serialization format.
Overall, great work. I can assist you in implementing it.
There is one problem, though it may be part of the materials you already referenced: the tree must be constructed identically by all parties, and from any state. And all binary-tree structures are insert-order dependent, unless you're storing them in some sort of trie. Specifying an insert order doesn't work, because someone constructing from scratch doesn't know how someone updating from a previous tree will insert them. But I wouldn't want to go to a basic trie, due to the space inefficiency. Something like a Patricia tree/trie would probably work, but it's very difficult to implement (correctly) and there's not a lot of existing, trusted implementations out there.
(EDIT: Sorry, this is basically what socrates above. I should have read the whole thread first:)
This is a non-issue; simply specify the order of insertion/deletion. For example: “Process blocks in order; for each block process transactions in order; and for each transaction first delete all inputs (in order) from, then insert all outputs (in order) into the alt-chain Merkle tree”. You might have to throw a special case in there for transactions that have as input the output of a transaction that occurs later in the same block (is that even allowed?).
Why (and how) would you be creating a tree from scratch without either access to the blockchain or the tree in the last alt-chain checkpoint?
Consider 10 unspent-TxOuts, {0,1,2,3,4,5,6,7,8,9}.
You and I are both constructing the same binary/red-back tree, except that you are starting from scratch and I am starting from a tree where elements {0,1,2,5,6,9,13} are part of the tree.
I have to add {3,4,7,8} and remove {13} from my tree. You just add all 10 elements in a specified order.
We're going to get different roots. I technically know how your tree would've been constructed, but I might have to start over and reinsert everything from scratch if I wanted to make sure my tree structure matches yours.
That's what I mean about "commutative computation" -- we need to make sure that regardless of whether you're starting from scratch, or updating an existing tree from any point in the past, that you'll get the same answer.
No, that's going in the wrong direction. Updates to the blockchain occur in atomic operations: blocks. Simply mandate that trees are constructed/updated according to the canonical ordering provided by the blockchain. If you insist on creating the search tree from scratch, simply replay the blockchain inserting and removing in the order specified therein. Or you can start from the tree of the last found alt-chain checkpoint, and replay insertions & deletions from that point forward.
Yes, order of operations matters, so standardize an order of operations.