tag:blogger.com,1999:blog-208437074950033830.post8785099924984406269..comments2023-03-16T07:08:52.010-05:00Comments on Cogitatio: Red-Black Tree in 2 hoursSal Manganohttp://www.blogger.com/profile/15017568083854549991noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-208437074950033830.post-6476895346663300032008-07-22T01:30:00.000-05:002008-07-22T01:30:00.000-05:00Okay, but Okasaki didn't say that deletion is neve...Okay, but Okasaki didn't say that deletion is never needed. He also didn't say that it can't be done with the smae big-O as in C.<BR/><BR/>In fact there's no fundamental problem with deletion, as the link I posted shows. And, the added complexity is not as bad as Okasaki suggests, in my opinion. <BR/><BR/>Leaving it out was more a matter of keeping the presentation concise, and then later I think he was overly defensive about it.Anonymoushttps://www.blogger.com/profile/02888491281001274822noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-65011251200053115322008-07-21T04:32:00.000-05:002008-07-21T04:32:00.000-05:00My guess is that the anonymous first commenter was...My guess is that the anonymous first commenter was referring to Okasaki's blog post on <A HREF="http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html" REL="nofollow">Ten Years of Purely Functional Data Structures</A>, where he says, <I>"...I only describe insertions, not deletions. There were two main reasons for that omission. First, deletions are much messier than insertions, and the introduction did not seem like the right place for a lot of messy details. Second, and more importantly, probably 95+% of uses of functional red-black trees don't need deletions anyway. Because the trees are immutable, when you want to delete something, you can simply revert back to a previous version of the tree from before the unwanted item was inserted. This is almost always both the easiest and the right thing to do. The exception is when you inserted something else that you want to keep after the item to be deleted, but this is extremely rare."</I><BR/><BR><BR/>I'm implementing this in Java, and I have to confess that I'd also really want my red-black trees to support deletion in arbitrary order.Matt Rhttps://www.blogger.com/profile/12089291649428164242noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-80252890893874803202008-05-09T04:35:00.000-05:002008-05-09T04:35:00.000-05:00In response to anonymous on the lack of a remove:Y...In response to anonymous on the lack of a remove:<BR/><BR/>You are wrong here, I think. It is just as easy to implement remove with O(log n) complexity.<BR/><BR/>As an example: <BR/>http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html<BR/><BR/>And, I don't see anywhere in the paper where Okasaki says you always want to remove in the reverse order.Anonymoushttps://www.blogger.com/profile/02888491281001274822noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-85005440851791251442008-05-06T09:09:00.000-05:002008-05-06T09:09:00.000-05:00jherber,Thanks for sharing that. How does the del ...jherber,<BR/><BR/>Thanks for sharing that. How does the del operation perform in practice for in order and reverse order deletions? random deletions?Sal Manganohttps://www.blogger.com/profile/15017568083854549991noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-4943564690430095412008-05-06T08:29:00.000-05:002008-05-06T08:29:00.000-05:00red black tree implementation used by scala:https:...red black tree implementation used by scala:<BR/><BR/>https://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/library/scala/collection/immutable/RedBlack.scala?rev=9646jherberhttps://www.blogger.com/profile/17138349998684867855noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-84718861458921168552008-05-06T01:57:00.000-05:002008-05-06T01:57:00.000-05:00Binstock and Rex's "Practical Algorithms" implemen...Binstock and Rex's "Practical Algorithms" implements complete red-black trees, and most other forms of trees. And it follows them up with a complete ISAM implementation to demo their use. Code is entirely in C.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-34546513466101981672008-05-06T01:49:00.000-05:002008-05-06T01:49:00.000-05:00Back in the early 90s (prior to the STL) I impleme...Back in the early 90s (prior to the STL) I implemented a Red/Black tree in C++. A more functional style than my approach at the time definitely would have made it easier to implement (which C++ templates goes a long way in helping). However, my clearest recollection is that deletes were the hardest things to get right!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-53370347017210711302008-05-05T21:39:00.000-05:002008-05-05T21:39:00.000-05:00Thanks Kalani. I just ordered that book from Amazo...Thanks Kalani. I just ordered that book from Amazon (unfortuntaly no Kindle edition yet).Sal Manganohttps://www.blogger.com/profile/15017568083854549991noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-31564967598729438132008-05-05T21:32:00.000-05:002008-05-05T21:32:00.000-05:00Sal, I think that your point about reading the Has...Sal, I think that your point about reading the Haskell implementation and grokking it quickly hits the nail on the head. The implementation may not have the same time/space complexity characteristics of the optimized C version, but as a vehicle to convey the idea of red-black trees, Okasaki's Haskell implementation is superior.<BR/><BR/>In fact, the most common example I've used to illustrate this point is QuickSort, which has an incredibly brief implementation in Haskell that clearly conveys the main idea. To get the best performance, though, you perform a number of "mostly dumb" transformations on the Haskell program to yield the more efficient C implementation (sort arrays instead of linked lists, choose the pivot at random rather than from the front, reuse/mutate a temporary array for the pivot-filter step, etc). The important lesson there for CS students (or practitioners) is to try to understand and solve the problem with the most natural notation, and only worry about optimization once the solution is well understood.<BR/><BR/>BTW, Okasaki has a very popular book on purely-functional data structures:<BR/><BR/>http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1210039860&sr=8-1<BR/><BR/>He recently posted a 10-year retrospective on lambda-the-ultimate:<BR/><BR/>http://lambda-the-ultimate.org/node/2665<BR/><BR/>It says a lot about the affect of this book that Peter van Roy (coauthor of "SICP 2.0") was so influenced by it early on.Kalani Thielenhttps://www.blogger.com/profile/01810792034258816216noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-44848503211849841632008-05-05T19:39:00.000-05:002008-05-05T19:39:00.000-05:00Luckily Mathematica is not a pure functional langu...Luckily Mathematica is not a pure functional language so I think there are ways for me to cheat and get good performance with out losing most of the simplicity. I have not proved this to myself yet but I'll post again when I know more.<BR/><BR/>However, a solution that can't remove is not completely useless. There are lots of problems that need a map where the map remains constant after initialization or only grows. Of course, if this is not your problem than this is not much help. <BR/><BR/>The real world is messy!!Sal Manganohttps://www.blogger.com/profile/15017568083854549991noreply@blogger.comtag:blogger.com,1999:blog-208437074950033830.post-58082181136594027442008-05-05T19:26:00.000-05:002008-05-05T19:26:00.000-05:00The problem with Okasaki's solution is that there ...The problem with Okasaki's solution is that there is no remove operation that can be performed with same Big-O complexity as a corresponding C-language implementation of remove. Okasaki hand waves around it by saying that you always want to remove elements from an RB Tree in the reverse order that it was inserted in, which is just totally lame. You can do this in Haskell by turning the RB Tree into a Monad, but that just makes the data structure imperative. However a fair comparison with C must implement the remove with same Big-O complexity, possibly as a Monad if not 100% functional.Anonymousnoreply@blogger.com