Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So I just learned red black trees at Cormen and wow! Typically I like to understand all algorithms and data structures to the point I can rebuild them from scratch without having to cheat looking at the pseudo code. I really like algorithms so I enjoy learning how they work and I usually go line by line and try some cases by looking at the code and checking if what's happening is what I understood that should happen.

Just understanding what's happening took me A LOT of time for RB trees. Even with the explanations of the book, I still found it hard to grasp the code. Not to mention that I couldn't understand how/why rotations work. I don't find it intuitive at all. I mean, the three (six actually) different cases for insertion and then the 4 cases for deletion? Is it possible to understand this thing? It's impossible for me to rebuild this code without cheating. Until binary tree I could implement the stuff out of my head, with some tweaking it would always work, but RB trees I'm not even going to try. I mean, even the teacher got confused sometimes so I suppose it's really not that easy, but at the same time, shouldn't we have to understand everything that's happening or at least why? The book didn't really explain how someone came up with the idea of rotations. How did someone notice that with 2 rotations you could solve any insertion problem? That's amazing!

My question is, do I really have to 100% understand RB trees? I feel kind of bad skipping stuff without fully understanding it. Thanks in advance guys! (PS: there's no tag for RB-tree, actually not even for tree, just binary-tree, so I only put algorithms)

share|improve this question

closed as primarily opinion-based by gnat, Bart van Ingen Schenau, MichaelT, Thomas Owens May 6 at 19:54

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

18  
"Young man, in mathematics you don't understand things. You just get used to them." -- John von Neumann –  delnan May 29 '11 at 21:03
2  
@Clash In what context? I don't think I've ever needed to know how RB trees work in a professional environment, but that might vary based on what you want to do. I'd say you're fine to skip 'em till you need 'em. –  Anna Lear May 29 '11 at 21:33
4  
@Clash It bothers me immensely that you say it's "cheating" to implement anything with guidance from an external source. The pseudocode exists for a reason - they eliminate the need to do it from memory. I completely agree with Winston: understanding and knowing from memory are two different mutually exclusive things. Memorising != understanding and understanding != memorising. –  doppelgreener May 29 '11 at 22:30
3  
It is ok to not actually care about RB trees - until I need them? –  Steven A. Lowe May 30 '11 at 2:25
1  
Maybe understand WHEN you should use RB trees, in preference to all the other types of tree implementation. Know what problems they solve, and all the reasons for choosing RB trees. But if you ever have to implement one (outside of an exam, of course), you'll be able to look it up; so why bother knowing how to do it from memory? –  David Wallace Dec 30 '11 at 10:17

6 Answers 6

up vote 12 down vote accepted

You seem to equate the idea of "understanding" with "being able to write the code without looking at the book." These are two different things. If you can see how rotating the tree nodes rearranges the tree in order to maintain balance, then you understand it. Being able to immediately recall all of the cases for which rotations apply isn't the point.

Myself, I could probably figure out the rotations if I had pen/paper/several hours to play with it. But I certainly couldn't just write it up without a thought. If I actually had to write such an algorithm, I'd look it up to make sure I was getting all the details right. Of course, in almost any situation I'd use already written code.

Where all of this comes in use is when you come across a situation that doesn't quite fit any of the algorithms. You will never need to write your own tree implementation. But you could find yourself, say, needing to flatten a heirachy of doubly-linked lists. In that case, having understood the basic idea behind rotation can be very helpful.

share|improve this answer
2  
'You seem to equate the idea of "understanding" with "being able to write the code without looking at the book." These are two different things.' Err... no. If you're writing this, it likely means you haven't studied maths much beyond a year or two of college, if even that. At some point, "understanding" maths (which, courtesy of Turing, equates to computing) is only about being able to demonstrate what you've "understood". There's no workaround or ifs or maybes or foo or bar or baz. At that level, if you can't prove your math assertion, you're toast. (Unless your name is Fermat.) –  Denis May 29 '11 at 22:46
13  
@Dennis, I have a M.S. in C.S. with an above-average amount of math courses for the major. I'm afraid that you haven't understood my point. Being able to prove or demonstrate what you understand is very important. Being able to memorize the details of a proof or method isn't. You SHOULD be able to write the code. But I don't see any use for a requirement to be able to write the code from MEMORY. –  Winston Ewert May 29 '11 at 23:26
2  
Be careful where you look it up too - IIRC, some textbooks have significant mistakes in their red-black tree algorithms. –  Steve314 May 30 '11 at 0:36
2  
@Steve314, you don't even need to understand RB to be a textbook author then! ;) –  Winston Ewert May 30 '11 at 0:54
    
Thanks Winston, this makes me relieved! There are only a couple of things that I didn't understand with the code that I might post in the near future. But I'm so glad that it's ok to not understand (by understand I mean writing the code without cheating) why/how someone noticed the 3/6 cases for insertion and 4/8 cases for deletion. –  Bernardo Pires May 30 '11 at 6:34

If you need "RB Trees By Heart" for your examination next week, you'll have to bite the bullet and learn them. In that case, you should reconsider your learning methods. Perhaps trying to explain RB Trees to a class mate will help you more than another night of lonesome code writing.

If RB Trees are a base for your next course after the vacations, skip them now (without bad feelings) and concentrate on this semester's course. But keep your eyes peeled for topics that could prepare you for a second attempt at RB Trees.

If you honestly feel that you'll never really need them (cf. Anna Lear's comment), kiss them goodbye without regret - nobody knows more that a drop in the sea of knowledge (just too bad that teachers often think their drop is the most important).

share|improve this answer

The key to programming success is to never give up:

Today its RB trees tomorrow it will be something else. The bigger lesson is not giving up.

For me, that's one of the core essence of programming, not giving up...

I would suggest that you keep trying, and when you fail DO IT AGAIN.

"Until you get, until it clicks, until it runs."

Because once you overcome the mountains, the sky becomes clear. Your mind shifts in understanding, you are temporally elevated (until the next mountain). This temporal elevation is worth more than all the money in the world..

share|improve this answer
    
Thanks, this was exactly my fear! If I give this up, what is stopping me from giving up the next thing? This is why I wasted almost a whole day just to understand insertion and deletion. –  Bernardo Pires May 30 '11 at 6:36
    
Its never a waste, believe me when it "clicks" the elevation more than makes up for all the sweat and tears. –  Darknight May 30 '11 at 9:13

If you're at all conversant with functional programming, you might find this approach to them better (Okasaki 1999):

http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf

If not, at least take heart from the opening sentence:

Everybody learns about balanced binary search trees in their introductory computer science classes, but even the stouthearted tremble at the thought of actually implementing such a beast.

share|improve this answer
    
Hahah ryan! That does make me relieved! Thanks a lot! Today I also noticed that there are very little questions on SO about RB-Trees. So I suppose they are really tricky. –  Bernardo Pires May 30 '11 at 6:35
2  
I think it's just that, aside from college CS students, they're the kind of thing that is implemented approximately once per programming language. (Or less. I think the most popular RB code for Scheme was ported from the RB code for OCaml.) –  Ryan Culpepper May 30 '11 at 11:57

You don't need to understand the rotations in detail. You should understand the relationship between RB trees and 2-3-4 trees (see Sedgewick). All those crazy rotations make a lot more sense when you think of them as 2-3-4 trees. If your professor hasn't taught RB trees as an implementation detail for 2-3-4 trees, you should probably read something on 2-3-4 trees. (Sedgewick's treatment is pretty good; Wikipedia doesn't have it.)

More generally, understanding the implementation details of why an algorithm works is only sometimes useful. Understanding the logic of why the algorithm works is almost always useful. Being able to come up with the algorithm yourself is usually not necessary, though the more algorithms you understand the better chance you'll have.

share|improve this answer

The best way to understand it is to try it out:

  • There are 3 or 6 rotations. Take a piece of paper and write them out one by one.
  • Once you get it, go and implement a Red Black Tree. It's OK if you have to look a few things up.

It's how we did it at college. And for the examination we got to explain how a part of it worked.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.