红黑树<黑高度>(重新起草)黑高度>
/** 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());
}
}
这是重新起草的,你认为这个会起作用吗?我已经在某些条件下对其进行了测试,并且还没有让我失望
/** 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());
}
}
This is redraft, do you think this one will work, i've tested it on certain conditions and as not failed me yet
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
所以我意识到你在这里使用java工作,但这里有一些伪代码可能会有所帮助:
我自己才刚刚开始尝试红黑树,但我相信这个算法应该为你提供你调用的任何节点上的黑色高度它来自。
编辑:我想我应该有资格,这将是在节点而不是树内找到的代码。 在 C++ 中,它将通过 someNode->blackHeight() 来调用。
So I realize that you're working in java here, but here's some pseudocode that may help:
I'm only just starting to experiment with red black trees myself, but I believe this algorithm should give you the black height on any node you call it from.
Edit: I guess I should qualify, this would be code found within a node not within the tree. In c++ it would be called with a someNode->blackHeight().
据我所知,您仅检查树上最左边和最右边路径的黑色高度。 红黑树的定义要求所有路径上的黑色高度相同。 例如,您的程序不会标记此无效树:
此外,它不会检查循环或键是否按顺序排列。
As far as I can tell, you're checking black height only on the leftmost and rightmost paths down the tree. The definition of a red-black tree requires that black height be the same on all paths. For example, this invalid tree is not flagged by your program:
Also, it doesn't check for cycles or if the keys are in order.