二分搜索树平衡
我在这里有一个问题,但没有保存。我在平衡完全不平衡的树(右侧的节点 1-15)时遇到问题。
我遇到了麻烦,因为我遇到了堆栈溢出。
> // balancing
public void balance(node n) {
if(n != null) {
System.out.println(height(n)-levels);
if (height(n.RCN) != height(n.LCN)) {
if (height(n.RCN) > height(n.LCN)) {
if(height(n.RCN) > height(n.LCN)) {
n = rotateL(n);
n = rotateR(n);
} else {
n = rotateL(n);
}
} else {
if(height(n.LCN) > height(n.RCN)) {
n = rotateR(n);
n = rotateL(n);
} else {
n = rotateR(n);
}
}
balance(n.LCN);
balance(n.RCN);
}
}
}
// depth from node to left
public int heightL(node n) {
if (n == null)
return 0;
return height(n.LCN) + 1;
}
// depth from node from the right
public int heightR(node n) {
if (n == null)
return 0;
return height(n.RCN) + 1;
}
// left rotation around node
public node rotateL(node n) {
if (n == null)
return null;
else {
node newRoot = n.RCN;
n.RCN = newRoot.LCN;
newRoot.LCN = n;
return newRoot;
}
}
// right rotation around node
public node rotateR(node n) {
if (n == null)
return null;
else {
node newRoot = n.LCN;
n.LCN = newRoot.RCN;
newRoot.RCN = n;
return newRoot;
}
}
I had a quesiton here, but it didn't save. I'm having trouble balancing a fully unbalanced tree (nodes 1-15 along the right side).
I'm having trouble because I get stack overflow.
> // balancing
public void balance(node n) {
if(n != null) {
System.out.println(height(n)-levels);
if (height(n.RCN) != height(n.LCN)) {
if (height(n.RCN) > height(n.LCN)) {
if(height(n.RCN) > height(n.LCN)) {
n = rotateL(n);
n = rotateR(n);
} else {
n = rotateL(n);
}
} else {
if(height(n.LCN) > height(n.RCN)) {
n = rotateR(n);
n = rotateL(n);
} else {
n = rotateR(n);
}
}
balance(n.LCN);
balance(n.RCN);
}
}
}
// depth from node to left
public int heightL(node n) {
if (n == null)
return 0;
return height(n.LCN) + 1;
}
// depth from node from the right
public int heightR(node n) {
if (n == null)
return 0;
return height(n.RCN) + 1;
}
// left rotation around node
public node rotateL(node n) {
if (n == null)
return null;
else {
node newRoot = n.RCN;
n.RCN = newRoot.LCN;
newRoot.LCN = n;
return newRoot;
}
}
// right rotation around node
public node rotateR(node n) {
if (n == null)
return null;
else {
node newRoot = n.LCN;
n.LCN = newRoot.RCN;
newRoot.RCN = n;
return newRoot;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
执行
rotateL
后跟rotateR
最终不会执行任何操作,因为您正在修改同一节点。n
不是原来的n
。它是函数中的newNode
。所以基本上,n
是这样的:所以你基本上保持树不变。
我也不确定为什么要重复
if (height(n.RCN) > height(n.LCN))
检查。我认为你的意思是你的第一次检查更像是abs(height(n.RCN) - height(n.LCN)) > 1
然后使用比较来确定旋转的方向。另外,您可以添加
height(...)
的实现吗?Doing a
rotateL
followed by arotateR
ends up doing nothing since you are modifying the same node.n
is not the originaln
. It is thenewNode
from the function. So basically,n
is something like this:So you are basically leaving the tree unchanged.
I am also unsure as to why you repeat the
if (height(n.RCN) > height(n.LCN))
check. I think you meant your first check to be more likeabs(height(n.RCN) - height(n.LCN)) > 1
and then use the comparison to determine which way to rotate.Also, could you add the implementation for
height(...)
?