Binary Search Tree Balancing
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 = ne开发者_如何学编程wRoot.RCN;
newRoot.RCN = n;
return newRoot;
}
}
Doing a rotateL
followed by a rotateR
ends up doing nothing since you are modifying the same node. n
is not the original n
. It is the newNode
from the function. So basically, n
is something like this:
newNode = rotateL(n);
n = rotateR(newNode);
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 like abs(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(...)
?
精彩评论