I feel things work most intuitively if the undo/redo functions simply navigate the history, but do not themselves form part of the history.
The history sequence would then be:
(t) --U-> (t-x) --U'-> (t)
And if you add (A) some new content (c) when in state (t-x), it becomes command , which can itself be undone with commands U'' (to remove A), U''' (to remove U):
(t) --U-> (t-x) --A-> (t+c) --U''--> (t-x) --U'''--> (t)
Ahhhhh, some time you should try a little app called Adobe Photoshop.