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

Das ist neu formulieren, denken Sie, das wird man arbeiten, ich habe es unter bestimmten Bedingungen getestet und als nicht bestanden mich noch nicht

Answer 1

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

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

Auch dann, wenn es nicht für die Zyklen überprüfen oder wenn die Schlüssel sind in Ordnung.

Answer 2

So merke 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 gerade erst selbst mit roten schwarzen Bäumen zu experimentieren beginnen, aber ich glaube, dieser Algorithmus sollte man die schwarze Höhe auf jedem Knoten geben Sie es aus aufrufen.

Edit: Ich glaube, ich qualifizieren sollte, dieser Code innerhalb eines Knotens nicht innerhalb des Baumes gefunden wäre. In c ++ wäre es mit einer someNode-> blackHeight () aufgerufen werden.

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