Rot Schwarz Baum <Schwarz Höhe> (Neuentwurf)

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

Dies ist umformulieren, denken Sie, das wird man arbeiten, habe ich es auf bestimmten Bedingungen getestet und als nicht bestanden mich noch nicht

Answer 1

Soweit ich das beurteilen kann, überprüfen Sie die schwarze Höhe nur auf den äußersten linken und rechten Pfaden. Die Definition eines rot-schwarzen Baums erfordert, dass die schwarze Höhe auf alle Pfade gleich ist. Zum Beispiel wird dieser ungültig Baum nicht von Ihrem Programm markiert:

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

Auch ist es nicht für die Zyklen überprüft oder wenn die Schlüssel sind in Ordnung.

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

So weiß ich, dass Sie hier in Java arbeiten, aber hier einige Pseudo-Code, die helfen können:

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 

Ich bin nur gerade mich mit roten schwarzen Bäumen zu experimentieren beginnen, aber ich glaube, dieser Algorithmus sollte dir die schwarze Höhe auf jedem Knoten geben, von dem du ihn nennst.

Edit: Ich denke, ich sollte qualifizieren, das wäre Code innerhalb eines Knotens nicht innerhalb der Struktur gefunden werden. In C++ würde es mit einem someNode-> blackHeight() aufgerufen werden.