Is it ok to not fully understand RB Trees? [closed]

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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).

Answer 5

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..

Answer 6

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.