c++ - 检查树是否满足Red Black Tree的black-height属性

如何递归检查给定的红黑树是否遵守“从节点到空链接的每条路径必须包含相同数量的黑节点”的规则。
我正在使用此结构:

enum color = {RED, BLACK};

typedef struct node {
    int value;
    struct node* left;
    struct node* right;
    color c;
} node;

我尝试使用此原型(prototype)实现算法:

bool isRBT(struct node* tree, int numberBlackNodesLeft, int numberBlackNodesRight)

但是，我无法递归计算这些数字。因为，该规则强加来自一个节点的每条路径都必须遵守该规则。这对我来说很难实现。

有什么好主意吗？

提前致谢!

最佳答案

这是一种简单的方法:

// Returns the number of black nodes in a subtree of the given node
// or -1 if it is not a red black tree.
int computeBlackHeight(node* currNode) {
    // For an empty subtree the answer is obvious
    if (currNode == NULL)
        return 0;
    // Computes the height for the left and right child recursively
    int leftHeight = computeBlackHeight(currNode->left);
    int rightHeight = computeBlackHeight(currNode->right);
    int add = currNode->color == BLACK ? 1 : 0;
    // The current subtree is not a red black tree if and only if
    // one or more of current node's children is a root of an invalid tree
    // or they contain different number of black nodes on a path to a null node.
    if (leftHeight == -1 || rightHeight == -1 || leftHeight != rightHeight)
        return -1;
    else
        return leftHeight + add;
}

要测试一棵树是否满足“红黑树”的black-height属性，可以将上述函数包装为:

bool isRBTreeBlackHeightValid(node* root)
{
    return computeBlackHeight(root) != -1;
}

关于c++ - 检查树是否满足Red Black Tree的black-height属性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27731072/