빨간 검은 나무 <블랙 높이> (레드 레이트)

Question

/** 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());
    }
}

이것은 redraft입니다. 당신은 이것이 효과가 있다고 생각하십니까, 나는 특정 조건에서 그것을 테스트했으며 아직 실패하지 않았습니다.

Answer 1

내가 알 수있는 한, 당신은 나무 아래에서 가장 왼쪽과 가장 오른쪽 경로에서만 검은 높이를 확인하고 있습니다. 붉은 검은 나무의 정의는 검은 높이가 동일해야합니다. 모두 경로. 예를 들어,이 잘못된 트리는 프로그램에 의해 표시되지 않습니다.

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

또한 사이클을 확인하거나 키가 순서대로 확인되지 않습니다.

Answer 2

그래서 나는 당신이 여기에서 Java에서 일하고 있다는 것을 알고 있지만, 여기에 도움이 될 수있는 의사 코드가 있습니다.

unsigned int blackHeight()
  height, heightLeft, heightRight = 0
  if black
    height++
  if left
    heightLeft = left->blackHeight()
  else
    heightLeft = 1
  if right
    heightRight = right->blackHeight()
  else
    heightRight = 1
  if heightLeft != heightRight
    //YOU HAVE A PROBLEM!
  height += heightLeft
  return height

나는 단지 붉은 검은 나무를 직접 실험하기 시작했지만이 알고리즘은 당신이 그것을 부르는 노드에서 검은 높이를 제공해야한다고 생각합니다.

Answer 3

 //enter code here

    private static void blackHeight(rbnode root) {
        if (root == null)
            return; 

        if (root.color == "black") {
            root.black_count = root.parent.black_count+1;

        } else {
            root.black_count = root.parent.black_count;
        }
        if ((root.left == null) && (root.right == null)) {              
            bh = root.black_count;              
        }               
        blackHeight(root.left);
        blackHeight(root.right);
    }