java - 红黑树<黑高>(Redraft)

/** The following function checks the red black tree black height
* @param n the root node is inputed then a traversal is done to calculate the black-height
* @return Return an error message / mesages informing the user whether or not the black height was maintained
* @author Ferron Smith
*/

public static void getCount (SkaRedBlackTreeNode skaRedBlackTreeNode) {
    VizRedBlackTreeNode n = skaRedBlackTreeNode.getVizRep();
if (validRoot(n))
    {
        static int lcount = leftCount(n);
        static int rcount = rightCount(n);

        if (rcount == lcount) {
            n.displayMsg("Black height maintained");
        }
        else
            // n.displayWarning("rcount " + rcount + " lcount " + lcount);
            n.displayError("Red Black Tree is unbalanced");
    }
}

/** The following function counts all the black node of the left side of the tree
 * @param n the left child is inputed and a traversal is done to count all the black nodes
 * */
public static int leftCount (VizRedBlackTreeNode n)
{
        if (n == null)
        return 0;
        else if (n.getrbtColr() == Color.black)
                return 1 + leftCount(n.getLeft());
        else
            leftCount(n.getLeft());
}

/** The following function counts all the black node of the right side of the tree
 * @param n the right child is inputed and a traversal is done to count all the black nodes
 * */
public static int rightCount (VizRedBlackTreeNode n)
{
    if (n == null)
    return 0;
    else if (n.getrbtColr() == Color.black) {
            return 1 + rightCount (n.getRight());
    else
        rightCount(n.getRight());
    }
}

这是重新起草的程序，您认为该程序可以工作，我已经在某些条件下对其进行了测试，但还没有使我失望

最佳答案

据我所知，您仅在树的最左侧和最右侧路径上检查黑色高度。红黑树的定义要求所有路径上的黑高度都相同。例如，您的程序未标记此无效树：

      B
     / \
    /   \
   /     \
  B       B
 / \     / \
B   R   R   B

另外，它不会检查循环或按键是否正确。