如何检查所有路径的节点的黑色高度到其后代叶？ [英] How to check the black-height of a node for all paths to its descendent leaves?

问题描述

给定一个红黑树，我需要编写一个高效算法，用于检查每个节点是否从节点到后代的所有路径都包含相同的黑色节点的数量，即如果属性为true或否则算法应该返回一个布尔值。

Given a red-black tree, I need to write an efficient algorithm that checks whether for each node, all paths from from the node to descendant leaves contain the same number of black nodes, i.e. the algorithm should return a boolean if the property is true or false otherwise.

推荐答案

它返回RB树的黑色高度。如果高度为0，则树是无效的红黑树。

It wiil return the black height of the RB-tree. If the height is 0, the tree is an invalid red black tree.

int BlackHeight(NodePtr root)
{
    if (root == NULL) 
        return 1;

    int leftBlackHeight = BlackHeight(root->left);
    if (leftBlackHeight == 0)
        return leftBlackHeight;

    int rightBlackHeight = BlackHeight(root->right);
    if (rightBlackHeight == 0)
        return rightBlackHeight;

    if (leftBlackHeight != rightBlackHeight)
        return 0;
    else
        return leftBlackHeight + root->IsBlack() ? 1 : 0;
}

这篇关于如何检查所有路径的节点的黑色高度到其后代叶？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！