CODEWITHSUNDEEP
algorithmdata-structuresred-black-tree
Paul Kelly
Paul Kelly

Reputation: 4019

Is there an easy way to remember the rotation methods for red-black trees?

Is there an easy way to remember the rotation methods for red-black trees?

Upvotes: 1

Views: 1103

Answers (2)

Dimitris Andreou
Dimitris Andreou

Reputation: 8898

No. There is no way to remember!! (Well, not really, but it is the most appropriate answer with regards to your use of your own time).

You know what? Nobody needs to be able to recite the exact mechanics of the rotations. Not even the handful of people required to implement these, need to remember them! See Java's implementation of TreeMap, which is a red-black tree, and search for "From CLR". They basically copy-pasted the code, which is exactly the proper course of action here.

Upvotes: 1

Aryabhatta
Aryabhatta

Reputation:

Perhaps they are looking for the equivalence of 2-3-4 trees (B-trees of degree 2) and red-black trees?

I have always found insertion in B-Trees easier to understand than insertion in red-black trees.

See the page here: http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html

In any case, you can probably just derive the rotations needed on the spot, it is not really that hard, once you have been familiar with them.

Upvotes: 2

Related Questions