What is a red-black-tree

  • A red-black-tree is a self-balancing binary search tree

  • Each node has a color bit which represents its color:   red or black

  • Properties of a red-black-tree:

      1. Root property: the root node is (always) black

      2. External property: every external node is black

      3. Red property: the children node of a red node are black

      4. Depth property: all external nodes have the same "black depth" (= # black nodes from root node to external node)

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer:

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer: no - the root property is violated

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer:

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer: no - the depth property is violated

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer:

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer: YES !!!

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer:

     

The red-black-tree

  • Is this tree a red-black-tree ?

  • Answer: no - the red property is violated