赤黒木<ブラック高さ>（再投稿）

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

これは再投稿です、あなたはこの1つが動作すると思います、私は特定の条件でそれをテストし、まだ

Answer 1

私を失敗していませんでした私が知る限り、あなたはツリーの左端と右端のパスだけで黒い高さを確認しています。赤黒のツリーの定義では、黒の高さはすべてのパスで同じにする必要があります。たとえば、この無効なツリーは、プログラムによってフラグが付けられていません。

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

また、サイクルの間またはキーを順になっているかどうかをチェックしません。

Answer 2

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

Answer 3

だから私はあなたがここに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 

私はちょうど赤黒木で自分自身を実験し始めたが、私よこのアルゴリズムはあなたがそれを呼び出すノードの黒い高さを与えるはずです。

編集：私は修飾する必要があります、これは、ツリー内のノード内に見つからないコードです。 C++ではsomeNode-> blackHeight（）で呼び出されます。