Balanced search trees

Any balanced search tree becomes persistent by path copying: an insert or delete copies the O(log n) nodes on its search path and leaves the rest shared, a method found independently by Myers, by Krijnen and Meertens, by Reps, Teitelbaum and Demers, and by Swart. Red-black trees are the usual choice. Okasaki’s 1999 functional pearl showed an insertion “any competent programmer should be able to implement in fifteen minutes or less”, with every rebalancing case handled by one small balance function.

Deletion was the missing piece: Okasaki’s book left it as an exercise, and Stefan Kahrs’s widely copied version enforces the invariants with types and is hard to transliterate. In 2010 Matt Might published a simpler delete that temporarily allows two extra colours, double black and negative black, and splits the work into remove, bubble and balance; an algorithm inspired by it was later published in the Journal of Functional Programming as “Deletion: The curse of the red-black tree”.

Haskell’s Data.Map uses weight-balanced trees instead (Adams 1993, after Nievergelt and Reingold’s trees of bounded balance), which keep a size in every node; Scala’s TreeMap and TreeSet are red-black trees. Choose these over a hash trie when you need ordered iteration, ranges or the smallest key.