Красного Черного Дерево <Черный Высота> (Переформулировать)

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

Это пересоставить, как вы думаете, это один будет работать, я опробовал его на определенных условиях и не подводил меня еще

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().