Проверить, является ли дерево удовлетворяет черный-высота собственностью красный черный дерево

Как рекурсивно проверить, соблюдает ли данное красное черное дерево правило "каждый путь от узла до нулевой ссылки должен содержать одинаковое количество черных узлов". Я использую эту структуру: 

enum color = {RED, BLACK};

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

Я попытался реализовать алгоритм, используя этот прототип: 

bool isRBT(struct node* tree, int numberBlackNodesLeft, int numberBlackNodesRight)
Но я не смог рекурсивно подсчитать эти числа. Потому что правило предписывает, что каждый путь от одного узла должен отражать правило. Что было довольно трудно для меня осуществить.

Любая блестящая идея, пожалуйста ?

Заранее спасибо!

1 2
algorithm red-black-tree

1 ответ:

Вот простой способ сделать это: 

// 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;
}
5