I have made a red-black tree and I think that it is not valid. Could someone please verify?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes and these NULL nodes are considered to be black.
So, by this logic, if we consider the order root->left->left->left as black, then no. of black nodes to that NULL node are 2.
Also, if we consider the node root->right->right->right->right->right as black, then no of black nodes to that NULL node are 3.
So, according to the above argument, it should not be a valid red-black tree.
Am I right or am I missing some important concept?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
You are correct $-$ the red-black tree you have drawn is not balanced.
For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed.
However for your tree, the path 00 results in a black height of $2$ and the path 1000 results in a black height of $3$. 0 = go left, 1 = go right.
