Красно-черное дерево <Черная высота> (перерисовка)
-
05-09-2019 - |
Вопрос
/** 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());
}
}
Это переработанный вариант, как вы думаете, этот вариант сработает, я протестировал его на определенных условиях и еще не подвел
Решение
Насколько я могу судить, вы проверяете высоту черного только на крайнем левом и крайнем правом пути вниз по дереву.Определение красно-черного дерева требует, чтобы высота черного дерева была одинаковой. все пути.Например, это недопустимое дерево не помечено вашей программой:
B
/ \
/ \
/ \
B B
/ \ / \
B R R B
Кроме того, он не проверяет наличие циклов и исправность ключей.
Другие советы
Я понимаю, что вы здесь работаете в 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
Я только начинаю экспериментировать с красно-черными деревьями, но считаю, что этот алгоритм должен дать вам высоту черного на любом узле, из которого вы его вызываете.
Редактировать:Думаю, мне следует квалифицировать, это будет код, найденный внутри узла, а не внутри дерева.В С++ он будет вызываться с помощью someNode->blackHeight().
//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);
}