A Java implementation of persistent red-black trees open sourced

Make search go mega fast! O(log(n)) inserts and deletes on ordered lists, but with the twist that the original list before modification remains intact! Implemented by using path-copying as per “Making Data Structures Persistent” Driscoll, Sarnak, Sleator and Tarjan.

PersistentRedBlackTreeSet

This was quite tricky to implement, because you are not allowed parent pointers, so you got to keep a linked list for the way back up when diving down, whose integrity can’t be compromised when you are doing the red-black spaghetti balancing act.

4 thoughts on “A Java implementation of persistent red-black trees open sourced

  • Hello,

    is there any particular reason why this code is GPL? It would be nice if it was less restrictive license, like Apache License. Then your code could be used in commercial projects.

    Regards

  • Yeah, new licenses are available on request. If you got a particular
    project in mind then send me the details at tom.larkworthy att gmail
    dot com and I’ll consider giving you a different license. GPL is just
    the default position.

    Tom

Leave a Reply

Your email address will not be published. Required fields are marked *

+ 27 = 37