Eh, I imagine it should be possible to maintain an out-of-line skip-list or an array of tombstones or something to deal with deletion/tag mutation (although in my experience with ASTs that's not that common of a requirement); and allocation can be done quite effectively with the help of the good old .bss section: just grab couple of millions of every type of node at the program's startup, virtual memory is almost free.