- Notifications
You must be signed in to change notification settings - Fork932
Closed
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 20If 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 20Do 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.
Metadata
Metadata
Assignees
Labels
No labels