红黑树的黑色height属性检查 [英] Red black tree black height property check

问题描述

给定一个RB树，我需要写一个有效的算法来检查是否为每个节点，从该节点的所有路径后代叶中含有的黑色结点相同。

Given a RB 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.

即。返回一个布尔值，如果该属性为true，否则为false。

i.e. returns a boolean if the property is true or false otherwise.

推荐答案

据wiil返回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;
}

这篇关于红黑树的黑色height属性检查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！