Sedgwick's more efficient Left-Leaning Red-Black Trees

[xytroxon]

I saw this and thought Lutz might be interested. It is also of interest to other newLISPers who want to understand one of the core aspects of the inner working of newLISP.

From the newLISP FAQ:

6. Does newLISP have hash tables?

newLISP has fast and scalable symbol processing using red-black binary trees . Symbols in newLISP are used to build dictionaries for associative data access, similar to how hash tables are used in other scripting languages. See the newLISP manual for more details.

While some people scoff at the use of Red-Black Binary Trees in newLISP over hash tables. To me, they are the compelling reason I am drawn to use newLISP ;)

See: Problems with Hash Tablers:

http://enfranchisedmind.com/blog/2008/02/25/problems-with-hash-tables/">//http://enfranchisedmind.com/blog/2008/02/25/problems-with-hash-tables/



Now there appears to be a better method to impliment this data structure!



Robert Sedgewick, of the Department of Computer Science at Princeton University, recently gave a talk on an improved version of Red-Black trees called, Left-Leaning Red-Black Trees. (Sedgewick co-authored the 1978 paper that gave Red-Black Trees their name.)



In this talk, he shows how to reduce the Java code for Red-Black Trees from 400+ lines to under 80 lines. Yikes!!! (Although he doesn't show timings, the code reduction of this method should be more effiecent, hence faster.)



He also created an interesting PDF file on his talk, complete with explainations of how various Binary Tree methods work.

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf">//http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

(Note: 12+ megabyte Adobe PDF file.)



Dr. Robert Sedgewick is also the author of the famed "Algorithms in C/C++/Java" books.

http://www.cs.princeton.edu/~rs/">//http://www.cs.princeton.edu/~rs/



-- xytroxon

[Lutz]

Thanks for commenting on Red-Black Trees in newLISP and the interesting links. People post all this stuff about: "newLISP doesn't have hashes" without realizing that modern flavors of B-Trees may be a better alternative for associative memory access than using hashes.



RB-Trees are an important part in the newLISP source, and when better implementations like the LLRB-Trees come up, than that is very interesting.



Lutz

[itistoday]

RB-Trees are an important part in the newLISP source, and when better implementations like the LLRB-Trees come up, than that is very interesting.



Lutz

Interesting indeed... will they be making a debut in newLISP per chance? ;-)



Thanks xytroxon for sharing this, I'm sure I'll find this useful some day in my own code...

[xytroxon]

An interesting blog "Left-leaning red-black trees are hard to implement" (in C)...

http://www.canonware.com/~ttt/2008/04/left-leaning-red-black-trees-are-hard.html">//http://www.canonware.com/~ttt/2008/04/left-leaning-red-black-trees-are-hard.html

...I started implementing left-leaning red-black trees, expecting to spend perhaps 15 hours on the project. I'm here more than 60 hours of work later to tell you that left-leaning red-black trees are hard to implement, and contrary to Sedgewick's claims, their implementation appears to require approximately the same amount of code and complexity as standard red-black trees...



...One point of interest is that my benchmarks show it to be ~25% slower than my standard red-black tree implementation. The red-black bit twiddling overhead only accounts for about 1/5 of the slowdown. I attribute the other 4/5 to the overhead of transforming the tree on the down pass, rather than lazily fixing up tree structure violations afterward...

The code so far.

http://www.canonware.com/%7Ettt/rb.h">//http://www.canonware.com/%7Ettt/rb.h



A comment to the blog reads:

make sure to download the slides again, Sedgewick has updated the whole thing rather radically a couple of days ago.



among other changes, the trees became more symmetric, and also there is a link to a complete and supposedly-working Java implementation.



that's what we get for tracking research in progress. :)

Indeed!