Question

Can a node in a red black tree have one red and one black child?

我有以下树种,我在这里只字面。传单被忽略。

                   B
           R               B
       B       B       R       R 
     R   R       R

Answer 1

Yes, a node can have differently coloured children. See, for example, the diagram at the very top of the MathWorld article on R-B trees; you can verify that it satisfies all the requirements for a R-B tree, and one of its nodes has children of different colours. As, for that matter, does the example you gave.

Answer 2

Here s a good article on read-black trees in the context of learning data structure in Haskell.

http://scientopia.org/blogs/goodmath/2009/11/30/advanced-haskell-data-structures-red-black-trees/

The R-B tree criteria it gives are pretty clear. The children of a red node must be black, but a black-node s children aren t specified. The important point is that all the paths from a given node to to the leaves below it must have the same number of black nodes. Looking at your tree every path down from the root has 1 black node (2 if you count the root), so it s okay.

友情链接