I think there really is no silver bullet here. In many cases, a particular problem has a simple solution with a lot of state. To fully specify a pure function on that much state, you may need a lot of working memory.
In certain cases, you may be able to reduce the size of working memory through recursion or related techniques: "The red-black tree T without node X is the subtree on the left without node X if ... possibly rotated based on the color of the top node in subtree T' ..."
But sometimes, it really is simpler to just do things imperatively with mutable state: "First recurse into subtrees until you find node X. Then, unlink it from its parent. ... Rotate if its color is red. Repeat with parent node ..."
There are many things that are strictly simpler with mutable state. Most prominently I think are hash tables, but there are others. Not all programs are best-described as a composition of maps, folds, and filters.
In certain cases, you may be able to reduce the size of working memory through recursion or related techniques: "The red-black tree T without node X is the subtree on the left without node X if ... possibly rotated based on the color of the top node in subtree T' ..."
But sometimes, it really is simpler to just do things imperatively with mutable state: "First recurse into subtrees until you find node X. Then, unlink it from its parent. ... Rotate if its color is red. Repeat with parent node ..."
There are many things that are strictly simpler with mutable state. Most prominently I think are hash tables, but there are others. Not all programs are best-described as a composition of maps, folds, and filters.