Árvore Black Red (Nova redacção)
-
05-09-2019 - |
Pergunta
/** 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());
}
}
Esta é ressaque, você acha que isso será um trabalho, eu testei em certas condições e, como não me falhou
Solução
Tanto quanto eu posso dizer, você está verificando altura preto somente nos caminhos mais à esquerda e mais à direita para baixo da árvore. A definição de uma árvore rubro-negro exige que a altura negro ser o mesmo em todas caminhos. Por exemplo, esta árvore inválido não está sinalizado pelo seu programa:
B
/ \
/ \
/ \
B B
/ \ / \
B R R B
Além disso, ele não verifica para ciclos ou se as teclas estão em ordem.
Outras dicas
Então eu percebo que você está trabalhando em java aqui, mas aqui está um pseudocódigo que ajuda pode:
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
Eu estou apenas começando a experimentar com árvore rubro-negra mim, mas acredito que este algoritmo deve dar-lhe a altura preto em qualquer nó que você chamá-lo de.
Edit: Eu acho que eu deveria qualificar, este código seria encontrado dentro de um nó não dentro da árvore. Em c ++ seria chamado com um 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);
}