CODEWITHSUNDEEP
binary-treered-black-tree
Brandon Zink
Brandon Zink

Reputation: 11

Red-Black Tree clarification questions

I've been reading up on red-black trees and have two questions about them that have been bugging me. I'm still learning about them so sorry if these are obvious to a more experienced coder.

  1. If you insert a node into a red-black tree, balance the tree, and then delete the node, does it result in the same tree? Does it always? It seems to me like it does, but I'm not entirely sure.

  2. If you delete a red node with no children, balance the tree, and then re-insert the same node always result in the same tree? Always, sometimes, or never?

Again, sorry if there are trivial, I'm still learning and haven't found a good answer to these questions. Thanks in advance!

Upvotes: 1

Views: 57

Answers (1)

uSeemSurprised
uSeemSurprised

Reputation: 1834

The answer to your 1st question is no it does not lead to the same tree, below i have shown an example : 

         5(B)                        5(B)                   5(B)
     /          \        Del(3)    /      \     Ins(3)    /      \
   3(B)          9(B)    =====>   4(B)    9(B)  =====>  4(B)     9(B)
      \                                                 /
       4(R)                                          3(R)

As you can see the tree has changed.

The answer to the second question is yes it always result in the same tree, because when you delete a red node that has no children then no rebalancing happenns because no rules are violated, as the parent of a red node is always black node and when we add the red node again it takes the same place.

Here is the link to a visualization tool that may help clear more of your doubts : https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Upvotes: 0

Related Questions