balance fix
banban opened this issue · 9 comments
AVLTree.cpp balance void has incorrect values at left-left and right-right branches.
= 1 and <= -1
should be replaced with
= 0 and <= 0
correspondently
Because the initial height value of leaf nodes is 1, I think current version should work perfectly. However, I will check it as soon as possible.
You can test it here
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
using sequence
i99 i96 i3 i21 i32 i26 e32 i44 i62 i42 i90 i79 i85 e99
where i prefix means insert, and e - erase/remove. You may notice that after removing 99, at 96 it's not balanced (96's left is too high, compared to its right).
So, 0 is more accurate condition rather than 1 and -1
I checked the test case you gave step by step, and actually there is no violation as you mentioned. You can test it too with this snippet:
AVLTree<int> tree;
// i99 i96 i3 i21 i32 i26 e32 i44 i62 i42 i90 i79 i85 e99
tree.insert(99);
tree.display();
tree.insert(96);
tree.display();
tree.insert(3);
tree.display();
tree.insert(21);
tree.display();
tree.insert(32);
tree.display();
tree.insert(26);
tree.display();
tree.erase(32);
tree.display();
tree.insert(44);
tree.display();
tree.insert(62);
tree.display();
tree.insert(42);
tree.display();
tree.insert(90);
tree.display();
tree.insert(79);
tree.display();
tree.insert(85);
tree.display();
tree.erase(99);
tree.display();
The result is:
[99] - (1, 1)
┌───[96] - (1, 1)
[99] - (2, 2)
┌───[3] - (1, 1)
[96] - (3, 2)
└───[99] - (1, 1)
┌───[3] - (2, 2)
└───[21] - (1, 1)
[96] - (4, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (3, 2)
└───[32] - (1, 1)
[96] - (5, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (3, 2)
└───[26] - (1, 1)
[32] - (6, 3)
└───[96] - (2, 2)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (3, 2)
└───[26] - (1, 1)
[96] - (5, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
[26] - (6, 3)
┌───[44] - (1, 1)
└───[96] - (3, 2)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
[26] - (7, 4)
┌───[44] - (2, 2)
└───[62] - (1, 1)
└───[96] - (4, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
[26] - (8, 4)
┌───[42] - (1, 1)
┌───[44] - (3, 2)
└───[62] - (1, 1)
└───[96] - (5, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
[26] - (9, 4)
┌───[42] - (1, 1)
┌───[44] - (2, 2)
└───[62] - (6, 3)
┌───[90] - (1, 1)
└───[96] - (3, 2)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
┌───[26] - (5, 3)
┌───[42] - (1, 1)
└───[44] - (2, 2)
[62] - (10, 4)
┌───[79] - (1, 1)
┌───[90] - (2, 2)
└───[96] - (4, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
┌───[26] - (5, 3)
┌───[42] - (1, 1)
└───[44] - (2, 2)
[62] - (11, 4)
┌───[79] - (1, 1)
┌───[85] - (3, 2)
└───[90] - (1, 1)
└───[96] - (5, 3)
└───[99] - (1, 1)
┌───[3] - (1, 1)
┌───[21] - (2, 2)
┌───[26] - (5, 3)
┌───[42] - (1, 1)
└───[44] - (2, 2)
[62] - (10, 4)
┌───[79] - (1, 1)
┌───[85] - (2, 2)
└───[90] - (4, 3)
└───[96] - (1, 1)
Program ended with exit code: 0
Sorry mate,
But if you have a look at last case you may notice that 90 is a parent of 96 and 85
[62] - (10, 4)
┌───[79] - (1, 1)
┌───[85] - (2, 2)
└───[90] - (4, 3)
└───[96] - (1, 1)
which is not correct AVL tree behaviour. The correct rotation should promote node 85 to the parent of 79 and 96. Node 96 should be a parent of 90. As a result, you should have this:
...┌───[79] (left child)
───[85]
...└───[96] (right child)
......└───[90] (left child)
Please test it manually here https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
And you will see the problem
I have already tested the case manually, and this is not about rotations indeed. While erasing, there is two different approaches, and both are correct:
- Swap node to delete, and largest node in left subtree. (Your visualization uses this approach)
- Swap node to delete, and smallest node in right subtree. (This is my approach)
It is up to you,
I have discussed it with my uni professor and he believes that tree is not balanced.
Do the professor have any counter case that makes the tree unbalanced? I want to fix the problem if exist.
Look his vision correlates with AVL visualization tool
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
If you repeat all these steps in that tool you will see at the final step it will move node 85 to the top of 96.
Your code is correct in terms of a general binary tree, but not aligned with that AVL.
I proposed that fix to align the rotations.
Ooo okey, I saw the problem finally, and fixed it. Thank you.