Explain black height algorithm in Red-Black tree

user_8663422 0
Viewed 1173

I have looked around for a way to check this property of a red black tree: "Every path from a node to a null node must contain the same number of black nodes".

Most of the upvoted answers look like this:

// Return the black-height of node x.  If its subtrees do not have
// the same black-height, call attention to it.

private int checkBlackHeight(Node x) {
if (x == null)
  return 0;
else {
  int leftBlackHeight = checkBlackHeight(x.left) +
      (x.left.isBlack() ? 1 : 0);
  int rightBlackHeight = checkBlackHeight(x.right) +
      (x.right.isBlack() ? 1 : 0);
  if (leftBlackHeight != rightBlackHeight)
      complain("blackheight error", x);
  return leftBlackHeight;
  }
}

What I am confused about is, doesn't this code only check for the leftmost and rightmost paths down the tree? How does it check for the inner paths? e.g. In the tree below, it should check the path 11-9-8-.. and 11-16-18... but does it check 11-16-13- (some inner nodes) -...

         11
       /    \
      9     16
     / \    /  \
    8  10  13   18
   /\  /\  /\   / \

Thank you in advance!

tree data-structures algorithm
1 Answers

The reason the code ends up checking all the paths, the way I understand it at least, is because the function has both a "go left" and "go right" instruction, so for each node both left and right are explored, and so all the paths will be covered. Additionally, determining whether the left node is black simply determines whether to add one to the black path length (for each recursive call).

user_89459200
Related