So this means you will also have to rearrange the tree whenever
display properties change, which is more work, and non-trivial one at
that (access to overlay strings is not very efficient in Emacs, when
there are many of them).

And what happens with text that is covered with an invisible text
property? Does it disappear from the tree?

If you keep a single RBT only for overlays, this tree will be modified only in case of overlay change.

And if you have a single property "narrow from X to Y", and inside X and Y there is other property, in the moment when you compute something on this tree, you can simply jump from the node X to the node keeping offset Y. You can ignore what is inside the tree, and the jump is done logarithmically, because searching in RBT is guaranteed to be log in the worse time.

Your example shows clearly that it is better to make a separate tree for each class of properties, than keeping text together overlays , together with font locks in the same tree.