Search code examples
data-structurestreebinary-search-treered-black-tree

Properties of a red-black tree

      35 (black)
    /    \
  21      54 (whole row is red)
 /  \    /  \
14  27  42  74 (whole row is black)
              \
              90 (red)

Would this classify as a red-black tree, I have not spotted any violations. What are primarily the properties I should look out for besides you can't have two consecutive red nodes?

Solution

  • There are no violations in the above tree.

    The main properties to look out for are :

    1) Root is Black

    2) There cannot be 2 consecutive red nodes.

    3) You need to add NIL Nodes as leaf nodes, whose color is taken as black.

    4) The Black Depth of all nodes from the root is always the same, eg in the above case the Black Depth is 3 including the NIL Nodes on each path.

    You can read about them here : Red Black Tree Properties