CODEWITHSUNDEEP
red-black-tree
pmac89
pmac89

Reputation: 418

Red Black Tree Insertion Questions why rotate?

So I have a Red Black Tree as followed:

2 = Root Black
Children = 1 (Black/Left), 4 (Red/Right)
Children of 1 = NIL & NIL => Height of Black Subtree is then 2 
Children of 4 = 3 (Black/Left), 5 (Black/Right)
Children of 3 = NIL & NIL, Height of Black Subtree is then 2 
Children of 5 = 7 (Red/Right)& NIL, Height is still then of course 2.

So when I insert 6 (of course the color is red) and it goes to be the left child of 7. In this web app I am following, it does a rotation on 6 with 7. Why? It does not seem to violate any properties of the RBT from what I can see.

Note: Source web app is a Java web app that required 1.7 Source: http://gauss.ececs.uc.edu/RedBlackTester/redblack.html

Upvotes: 3

Views: 225

Answers (1)

pulasthi
pulasthi

Reputation: 1750

The properties of RBT are.

  1. Every node is either red or black.
  2. The root and leaves (NIL’s) are black.
  3. If a node is red, then its parent is black.
  4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x).

So if 7 is red and and when 6 is added its also red this violates the 3rd property hence the rotation and changes to remove the violations.

Upvotes: 3

Related Questions