If this is your first attempt to understand red-black tree, please watch this video lecture. It will give you a solid foundation. Next, before you start to this tutorial, make sure:

Conceptually, you are done here. All left now is some slight minor details about plumbing rotation and a couple of fine prints in algorithm like some times rotation may cause root node reassignment, how we treat a NIL node a black node, etc.

People claim there are two type of rotations -- right, when left child swaps with it's parent (i.e. moves to right); and left rotation, when a right child swaps with it's parent. Basically, if you start with a tree and right rotate a child, then left rotate the original parent the tree stays unchanged. (Figure out how and why the nodes are snipped and pasted the way they are.)

[1] View a foundation video lecture. it worth watching.

[3] View/download Java code for red-black tree from GitHub

[4] I haven't referred much from this chapter, but it may worth reading: Introduction to Algorithms: CLRS, chapter 13: Red-Black Trees

[5] The execution of the code for a sorted input

- You are not in a hurry. (In that case, just use the code from the link in footnote)
- You do not get impatient.
- You do not bother why it works. It works. Once you get the algorithm and code it, it will be much simpler to visualize how it works. But, for 'why' -- you may need to research.

**One Aim:**Approximately balanced tree creation. From root to leaf, no (simple) path is more than twice as long as any other.**Two Rules:**(CLRS says five, but others are trivial)*Color Constraint*: Red nodes will have both of it's children black. Black nodes can have either.*Number Constraint*: For each node, simple path to all the leaves will have same numbers of black children.

**Three Situations**: Couple of points to be noted before we see the*situations*- Wherever I refer Uncle, it means (same as in common life) -- "sibling of parent node", "the other child of node's parent's parent".
- We assume as NIL nodes of all the leaves are black.
- We always insert red node. So, We are not breaking #2: Number Constraint by adding a black node, but we are breaking constaint #1: Color Constraint.
- Keep the root node black. You will see, it makes life easier. It does not breaks any of the constraints.

*Situations*:*A Red uncle is a good uncle*: If newly inserted node has red uncle, we can fix the situation just by fixing colors. Invert parent, grand parent, and uncle's colors. Now we need to check if grandparent is satisfying the Color Constraint.*A black uncle on opposite side wants one rotation*: If the uncle is black, we got to rotate. A slightly better case is when the newly inserted node is left child of its parent and uncle is right child of its parent or vice versa. In that case, you make a left-rotation or a right-rotation (rotations will be discussed later in this post). And then fix colors.*A black uncle on the same side is double as dangerous*: A case when newly inserted node is right child and the black uncle is also right child or both are left children, you need to make a left-rotation if inserted node is right-child or right rotation if newly inserted node is left child. This will make it situation 2.

Conceptually, you are done here. All left now is some slight minor details about plumbing rotation and a couple of fine prints in algorithm like some times rotation may cause root node reassignment, how we treat a NIL node a black node, etc.

**Rotation:**A rotation is basically to swap a parent and child such that the BST property still holds. So,*why do we call it rotation?*Well, the process mutates the tree in such a way that it looks, to a casual observer, as if the tree just did a Toe Loop Jump. (well, this is the best I can explain.)People claim there are two type of rotations -- right, when left child swaps with it's parent (i.e. moves to right); and left rotation, when a right child swaps with it's parent. Basically, if you start with a tree and right rotate a child, then left rotate the original parent the tree stays unchanged. (Figure out how and why the nodes are snipped and pasted the way they are.)

**The algorithm:**(Please note the below is not a valid Python code, I have use Python-esque code so that code highlighter shows key areas)root = NIL def insert (node) if root = NIL root = node root.color = BLACK return parent = root current = root while current != NIL parent = current if node.value < root.value current = current.left else current = current.right if node.value < parent.value parent.left = node else parent.right = node node.color = RED fixTree(node) def fixTree (node) if node.parent == RED uncle = getUncle(node) #case 1: Uncle Red if uncle.color = RED node.parent.color = BLACK node.parent.parent.color = RED uncle.color = BLACK fixTree(node.parent.parent) #Case 2, 3: Sirius Black. else if parentInLeftSubTree(node) #we are in left subtree, uncle is right child #case 3: rotate to case 2 if node.parent.right = node rotateLeft(node) #case 2: color fix and rotate node.color = BLACK node.parent = RED rotateRight(node) else #we are in right subtree, uncle is left child #case 3: rotate to case 2 if node.parent.left = node rotateRight(node) #case 2: color fix and rotate node.color = BLACK node.parent = RED rotateLeft(node) root.color = BLACK def getUncle (node) if node = NIL or node.parent = NIL return NIL parent = node.parent grandParent = parent.parent if grandParent = NIL return NIL if parent = grandParent.left return grandParent.right return return grandParent.left def parentInLeftSubTree (node) if node.parent = node.parent.parent.left return true else return false """ * g g * / / * x Left Rotation(y) y * / \ ----------------> / \ * alpha y <---------------- x gamma * / \ Right Rotation(x) / \ * beta gamma alpha beta """ def rotateLeft(y) x = y.parent g = x.parent alpha = x.left beta = y.left gamma = y.right y.parent = g if g != NIL if g.left = x g.left = y else g.right = y else root = y x.parent = y y.left = x x.right = beta if beta != NIL beta.parent = x def rotateRight(x) y = x.parent g = y.parent alpha = x.left beta = x.right gamma = y.right x.parent = g if g != NIL if g.left = y g.left = x else g.right = x else root = x x.right = y y.parent = x y.left = beta if beta != NIL beta.parent = y

**Footnotes:**[1] View a foundation video lecture. it worth watching.

**[2] Simulate your input on of a red-black tree creation -- here**

[3] View/download Java code for red-black tree from GitHub

[4] I haven't referred much from this chapter, but it may worth reading: Introduction to Algorithms: CLRS, chapter 13: Red-Black Trees

[5] The execution of the code for a sorted input

`a = {8, 11, 14, 18, 22, 23, 31, 37, 41, 47, 60, 74, 84, 87, 88, 97, 99}`

, generates the following tree
Hi Nishant,

ReplyDeleteI found this way to contact you. I want to ask a question about your post. I have tried this http://facebook.stackoverflow.com/questions/5058144/facebook-api-get-all-profile-pictures

To get an albums photo. But I am unable to do this.

here i am getting JSON array

var data = JSON.parse(e.result).data;

and here I am using it to get photos.

"https://graph.facebook.com/" + data[x].id + "/photos?access_token=" + Ti.Facebook.accessToken,

plz plz plz can you guide me to solve this problem.