شجرة سوداء حمراء <ارتفاع أسود> (Redraft)

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

لذلك أدرك أنك تعمل في Java هنا، ولكن هنا بعض Pseudoodocode قد تساعد:

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

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