Красное Черное Дерево <Black Height> (Редрафт) - PullRequest
Новая
       5

Красное Черное Дерево <Black Height> (Редрафт)

0 голосов
/ 26 мая 2009 
/** 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());
    }
}

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

Ответы [ 3 ]

4 голосов
/ 26 октября 2012

Итак, я понимаю, что вы здесь работаете в 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 ().

1 голос
/ 21 марта 2012 
 //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);
    }
1 голос
/ 26 мая 2009

Насколько я могу судить, вы проверяете высоту черного только на самых левых и правых путях вниз по дереву. Определение красно-черного дерева требует, чтобы высота черного была одинаковой на всех путях. Например, это недействительное дерево не помечено вашей программой: 

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

Кроме того, он не проверяет циклы или ключи в порядке.

...