Search code examples
algorithmdata-structuresred-black-tree-insertion

red black tree insertion

I inserted node 36 in the red black tree and the following red black tree resulted:

enter image description here

my problem is that how to handle double red in this special case? is it case 2 or 3?

Solution

  • Based on Wikipedia's properties and cases...

    36 would be inserted under case 5, rotating 22 left.

    The parent P is red but the uncle is black or not there.

    Wikipedia just says "the uncle is black", but, looking at the code, you'll see that that case triggers.

    Note that the tree without 36 was already invalid because property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not held:

    • 20 to 15 contains 1 black node
    • 20 to 30 contains 2 black nodes

    Assuming the insert order is 20, 15, 22, 30, 36...

    All nodes are inserted as red.

    22 would be inserted under case 2.

    The parent is black.

    30 would be inserted under case 3, making 22 and 15 black and 20 red.

    The parent and uncle are red; both are repainted black and the grandparent becomes red.

    36 would be inserted under case 5, rotating 22 left.

    The parent P is red but the uncle is black or not there.