Chris Angelico <ros...@gmail.com> writes: > Maybe I'm completely on the wrong track here, but the last time I > implemented a self-balancing tree, it usually involved a fair amount > of mutation.
AVL trees are fairly simple to implement without mutation. Red-black trees are traditionally implemented with mutation, inserting by making nodes mis-colored, then going and re-coloring them. But they can be done mutation-free as well. Here's an amazing Haskell implementation where the tree invariants are encoded in the datatype: https://gist.github.com/rampion/2659812 Reddit discussion of above: https://redd.it/ti5il More recent versions of GHC make the type signatures even nicer, since you can put numbers directly into types without that nested type encoding. -- https://mail.python.org/mailman/listinfo/python-list
