A question about balance function in AVL #33
Description
function balance(node) {
if (node.balanceFactor > 1) {
// left subtree is higher than right subtree
if (node.left.balanceFactor > 0) {
return rightRotation(node);
} if (node.left.balanceFactor < 0) {
return leftRightRotation(node);
}
} else if (node.balanceFactor < -1) {
// right subtree is higher than left subtree
if (node.right.balanceFactor < 0) {
return leftRotation(node);
} if (node.right.balanceFactor > 0) {
return rightLeftRotation(node);
}
}
return node;
}
When the node.balanceFactor > 1 and node.left.balanceFactor = 0, we do nothing with balance function.
As follows:
32 32
/ \ /
8 64* 8
/ \ / \ / \
4 16 48 128 --- remove the node-64 ---> 4 16
/ \ / \ / \ / \
2 6 10 20 2 6 10 20
If we use the balance as follows, (when node.left.balanceFactor = 0, we do RR rotation.):
function balance(node) {
if (node.balanceFactor > 1) {
// left subtree is higher than right subtree
if (node.left.balanceFactor < 0) {
return leftRightRotation(node);
}
return rightRotation(node);
} else if (node.balanceFactor < -1) {
// right subtree is higher than left subtree
if (node.right.balanceFactor > 0) {
return rightLeftRotation(node);
}
return leftRotation(node);
}
return node;
}
We can get this:
32 32
/ \ /
8 64* 8
/ \ / \ / \
4 16 48 128 --- remove the node-64 ---> 4 16
/ \ / \ / \ / \
2 6 10 20 2 6 10 20
8
/ \
--- balance the node-32 --> 4 32
/ \ /
2 6 16
/ \
10 20
Do you think so?
I'd like to make a quest if I may. I want to translate your articles into Chinese. I wish more people could make a look of these wonderful articles! May I?
Thank you very much.