You may also want to take a look at “Deletion: The curse of the red-black tree” (Germane and Might 2014), which presents functional deletion for red-black trees.

https://matt.might.net/papers/germane2014deletion.pdf