Red Tree Noir <Taille Noir> (Reformuler)

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

C'est reformuler, pensez-vous que celui-ci fonctionne, je l'ai testé sur certaines conditions et ne pas me manquaient encore

Answer 1

Pour autant que je sache, vous vérifiez la hauteur noire seulement sur les chemins les plus à gauche et les plus à droite en bas de l'arbre. La définition d'un arbre rouge-noir nécessite que la hauteur du noir soit la même sur tous les chemins. Par exemple, cet arbre est invalide pas marqué par votre programme:

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

En outre, il ne vérifie pas pour les cycles ou si les touches sont en ordre.

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

Alors je me rends compte que vous travaillez en java, mais voici quelques pseudocode qui peuvent aider:

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 

Je ne fait que commencer à expérimenter avec des arbres noirs rouges moi-même, mais je crois que cet algorithme devrait vous donner la hauteur noire sur n'importe quel nœud que vous l'appelez. Edit: Je suppose que je devrais qualifier, ce serait le code trouvé dans un nœud ne se trouve pas dans l'arborescence. En C++, il serait appelé avec someNode-> blackHeight().