Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation?

I've not researched very deeply into this subject matter but I see that Okasaki's implementation is left-leaning, and just as Yamamoto's.

Left-leaning red-black trees are considered to be harmful, so I'd like to know the reason behind this, if any.

  • 2
    $\begingroup$ The last link is talking about mutable left-leaning red-black trees and a very specific implementation: Sedgewick's 2008 formulation. Okasaki's red-black tree was from 1999. In general, mutable and immutable "versions" of data structures are better viewed as distinct data structures rather than variations of "one" data structure. All of this is fairly moot unless functional LLRB's are widely used, and that doesn't appear to be the case. I'm pretty sure none of Haskell's standard data structures are based on red-black trees of any sort, and O'Caml's Set and Map are AVL trees. $\endgroup$ – Derek Elkins Jun 12 '18 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.