tag:blogger.com,1999:blog-6555947.post3470947414503770428..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Notes from Dagstuhl I: Red-black treesSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-6555947.post-83685576435757937422008-03-06T04:02:00.000-07:002008-03-06T04:02:00.000-07:00this is life we have to sacrefice something to gai...this is life we have to sacrefice something to gain something<BR/> with regards<BR/> edgar dantas<BR/> www.gadgetworld.co.inAnonymoushttps://www.blogger.com/profile/09976782472523278151noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-38951252656637086592008-03-04T13:01:00.000-07:002008-03-04T13:01:00.000-07:00Can anyone comment on AVL trees (advantages/disadv...Can anyone comment on AVL trees (advantages/disadvantages)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-33886967436093150362008-02-27T13:25:00.000-07:002008-02-27T13:25:00.000-07:00My 2 cents about this.http://magic.aladdin.cs.cmu....My 2 cents about this.<BR/><BR/>http://magic.aladdin.cs.cmu.edu/2008/02/27/my-vote-goes-to-red-black/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-32963670988646182132008-02-26T16:34:00.000-07:002008-02-26T16:34:00.000-07:00> Sure, there is a mapping between 2-3-4> trees an...> Sure, there is a mapping between 2-3-4<BR/>> trees and RB trees. Problem is, I will likely<BR/>> be able to do only one of them. So the<BR/>> dilemma remains. <BR/><BR/>Here's one idea. Do 2-3-4 trees in class. State the 1-1 correspondence between left-leaning red-black trees and 2-3-4 trees to make the connection with binary search trees. Assign insertion for homework.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-47644341770840236862008-02-26T10:51:00.000-07:002008-02-26T10:51:00.000-07:00Sure, there is a mapping between 2-3-4 trees and R...Sure, there is a mapping between 2-3-4 trees and RB trees. Problem is, I will likely be able to do only one of them. So the dilemma remains. <BR/><BR/>Cheers,Piotrhttps://www.blogger.com/profile/13283386044289655376noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-79854589233883930412008-02-25T19:58:00.000-07:002008-02-25T19:58:00.000-07:00> If you look at what Bob talks about in his notes...> If you look at what Bob talks about in his notes,<BR/>> seems that RB trees are "merely" a simpler a<BR/>> way of thinking about 2-3-4 trees, which<BR/>> are the "real" thing. <BR/><BR/>I think it's more accurate to say RB trees are the practical way to *implement* 2-3-4 trees. But it's simpler to think in terms of 2-3-4 trees.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-50390392460063916152008-02-25T17:06:00.000-07:002008-02-25T17:06:00.000-07:00If you look at what Bob talks about in his notes, ...If you look at what Bob talks about in his notes, it seems that RB trees are "merely" a simpler a way of thinking about 2-3-4 trees, which are the "real" thing. <BR/><BR/>In other words, the concept is made clear in 2-3-4 trees, and via a one-one correspondence between structures, the RB-tree simulates the 2-3-4 tree with "easier" code. <BR/><BR/>I don't know if that helps :)Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-16337616602113812512008-02-25T16:20:00.000-07:002008-02-25T16:20:00.000-07:00Very timely discussion - I am about to teach searc...Very timely discussion - I am about to teach search trees this Thursday (in an undergraduate algorithms class), and I am TORN between 2-3(-4) trees and RB-trees. The respective pros:<BR/><BR/>- RB-trees: are in the book (CLRS); examples of BINARY search trees; doable in finite time<BR/><BR/>- 2-3(-4)-trees: simple and intuitive search and insertion, although not deletion; no (risk of breaking your neck while tracing) rotations.<BR/><BR/>Any thoughts on this choice ? Also, any good lecture notes on 2-3(-4) trees out there ?<BR/><BR/>Thanks,Piotrhttps://www.blogger.com/profile/13283386044289655376noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-2080705130498151682008-02-25T10:55:00.000-07:002008-02-25T10:55:00.000-07:00Ah, seeing Suresh #4, I realize my writing was amb...Ah, seeing Suresh #4, I realize my writing was ambiguous. To set the record straight, deterministic skip list is by Munro, Papadakis and Sedgewick. Andersson is responsible for the simplified binarization of 2-3 trees. Sorry for the confusion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-46451792052777611892008-02-25T07:09:00.000-07:002008-02-25T07:09:00.000-07:00According to the slides the point is that both ins...According to the slides the point is that <I>both</I> insertion and deletion are easier. I'm just saying that there exist better implementations for insertion than the ones given as examples (Java API and Algorithms in Java), when measured by code complexity.<BR/><BR/>I don't know which would be a good existing implementation for deletions.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-60891910753165547722008-02-25T03:32:00.000-07:002008-02-25T03:32:00.000-07:00This RB implementation is quite short (but lacks d...<I>This RB implementation is quite short (but lacks deletion): </I><BR/><BR/>That is exactly the problem: deletion is complicated. AA-trees are similar in spirit to LRB trees, yet deletion is still marginally more complicated.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59036544745813508002008-02-25T01:37:00.000-07:002008-02-25T01:37:00.000-07:00This RB implementation is quite short (but lacks d...This RB implementation is quite short (but lacks deletion): http://www.eecs.usma.edu/webs/people/okasaki/sigcse05/RedBlack.javargrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-44040099017991044522008-02-24T21:21:00.000-07:002008-02-24T21:21:00.000-07:00Treaps. Do I have to say anything more?Yes? Oh we...Treaps. Do I have to say anything more?<BR/><BR/>Yes? Oh well - they do outperform orange-purple trees any day of the week (including sundays), and they are way way simpler. Whats much harder is the analysis, naturally.<BR/><BR/>Skip-lists are cute, but in fact inferior to yellow-gray trees, because they perform twice the number of memory allocations (a huge overhead in practice unless you write your own memory manager, and even then the locality of ref is going to be bad).<BR/><BR/>Naturally if the cache hierarchy is the bottleneck, b-trees, or some other io efficient, or cache obvious data structures should be used.<BR/><BR/>I remember seeing some paper comparing all this data structures with the treaps coming on top, and the rest being inferior.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-65534751585816948322008-02-24T19:22:00.000-07:002008-02-24T19:22:00.000-07:00In this day and age of multi-level cache hierarchi...In this day and age of multi-level cache hierarchies and memory access becoming ever slower than processor speeds, a plain old red-black or 2-3(-4) tree or even a skip list can bring along with it a pretty high constant factor (in terms of latency) for each pointer dereference.<BR/><BR/>What you need is locality of reference and even better contiguity of reference, as you obtain in B-trees and all their variants which database people had already sought out since they were working with the huge latencies of disks. But even memory-resident algorithms people should now also consider these factors ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-25683826727619660482008-02-24T17:53:00.000-07:002008-02-24T17:53:00.000-07:00So, this is interesting. Someone actually brought ...So, this is interesting. Someone actually brought up the Andersen skip list implementation during the discussion. I'm not sure how things were resolved: Raimund (Seidel) and Bob continued to discuss things later on.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-15217970068385940372008-02-24T16:08:00.000-07:002008-02-24T16:08:00.000-07:00There was some work on simplifying bst implementat...There was some work on simplifying bst implementations back in the 90s. I fondly remember "deterministic skip lists" and another design from Arne Andersson (Weiss's textbook call it AA-tree, iirc). Andersson's design, in particular, uses a similiar idea of restricting the encoding of 3-nodes in a 2-3 tree to be "right-leaning". The code is very clean too. It's great to see this cute idea get more popularized!<BR/><BR/>http://user.it.uu.se/~arnea/abs/simp.html<BR/>A. Andersson. Balanced search trees made simple. <BR/>In Proc. Workshop on Algorithms and Data Structures, pages 60--71. Springer Verlag, 1993.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-71493663144161721832008-02-24T16:03:00.000-07:002008-02-24T16:03:00.000-07:00I'm not sure. Bob was arguing that that the code s...I'm not sure. Bob was arguing that that the code simplicity and length is such that it helps alleviate the increased number of steps needed to traverse the (generally longer) tree. But again, I didn't see detailed proofs. <BR/><BR/>although come to think of it, I should have :), since he (and Phillipe Flajolet) push the idea of exact analysis.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-48184836174552039262008-02-24T13:14:00.000-07:002008-02-24T13:14:00.000-07:00Without sacrificing asymptotics -- but any sacrifi...Without sacrificing asymptotics -- but any sacrifice in the constant factors?Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.com