AVL tree can get imbalanced

[vanHavel]

Example of Problem

AVL* A = new AVL();

int n = 9;
int arr[] = {7, 4, 8, 2, 5, 9, 1, 3, 6};
for (int i = 0; i < n; i++) {
    A->insert(arr[i]);
}
A->remove(9);
BSTVertex* L = A->root->left; // make root public to check this
printf("%d\n", L->key);
printf("%d\n", L->height);
printf("%d\n", L->right == NULL);

After insertion of the 9 elements, the tree looks like this: After deletion of the 9, the tree looks like this: The tree is imbalanced at the 4 node, as it has height 2 but the right child is NULL.

What causes the issue

In the above example, the tree after deleting 9, and before rebalancing looks like this: The root is now imbalanced and needs to be rebalanced. This is the relevant rebalancing code:

int balance = h(T->left) - h(T->right);
if (balance == 2) { // left heavy
    int balance2 = h(T->left->left) - h(T->left->right);
    if (balance2 == 1) {
        T = rotateRight(T);
    }
    else { // -1
        T->left = rotateLeft(T->left);
        T = rotateRight(T);
     }

In the example, balance2 is 0, so we enter the else case, which causes left rotation of left child followed by right rotation. The tree after the left rotation of the left child: The tree after the right rotation of the root (final result):

Suggested fix

Change the if condition in the rebalancing to

if (balance2 >= 0) {

to trigger the right rotation for the 0 case. This yields the following, correctly balanced tree: The same needs to be done for the symmetric case.

[stevenhalim]

Hi Lukas

The bug looks legit :O and I wonder why it has passed about ~5 years of algorithm classes in NUS :O without anybody noticing. I will go back to this PR as soon as https://ioi2020.sg/schedule is over.

Regards,

Steven Halim (Dr.) Senior Lecturer School of Computing, National University of Singapore http://www.comp.nus.edu.sg/~stevenha IOI 2020 (https://ioi2020.sg/) and 2021 (http://ioi2021.sg/) Deputy Director+IC Member https://visualgo.net and https://cpbook.net (CP4 is out)

On Mon, Sep 14, 2020 at 8:55 PM Lukas Huwald notifications@github.com wrote:

Example of Problem

AVL* A = new AVL();

int n = 9; int arr[] = {7, 4, 8, 2, 5, 9, 1, 3, 6}; for (int i = 0; i < n; i++) { A->insert(arr[i]); } A->remove(9); BSTVertex* L = A->root->left; // make root public to check this printf("%d\n", L->key); printf("%d\n", L->height); printf("%d\n", L->right == NULL);

After insertion of the 9 elements, the tree looks like this: [image: base] https://user-images.githubusercontent.com/9655322/93087024-49181b80-f698-11ea-9d7b-5a4339e78bea.png After deletion of the 9, the tree looks like this: [image: wrong2] https://user-images.githubusercontent.com/9655322/93087108-6947da80-f698-11ea-8b21-7bcc36267162.png The tree is imbalanced at the 4 node, as it has height 2 but the right child is NULL. What causes the issue

In the above example, the tree after deleting 9, and before rebalancing looks like this: [image: del] https://user-images.githubusercontent.com/9655322/93087259-98f6e280-f698-11ea-823e-a30348982b60.png The root is now imbalanced and needs to be rebalanced. This is the relevant rebalancing code:

int balance = h(T->left) - h(T->right); if (balance == 2) { // left heavy int balance2 = h(T->left->left) - h(T->left->right); if (balance2 == 1) { T = rotateRight(T); } else { // -1 T->left = rotateLeft(T->left); T = rotateRight(T); }

In the example, balance2 is 0, so we enter the else case, which causes left rotation of left child followed by right rotation. The tree after the left rotation of the left child: [image: wrong1] https://user-images.githubusercontent.com/9655322/93087575-0c98ef80-f699-11ea-8016-61a369517f83.png The tree after the right rotation of the root (final result): [image: wrong2] https://user-images.githubusercontent.com/9655322/93087108-6947da80-f698-11ea-8b21-7bcc36267162.png Suggested fix

Change the if condition in the rebalancing to

if (balance2 >= 0) {

to trigger the right rotation for the 0 case. This yields the following, correctly balanced tree: [image: right] https://user-images.githubusercontent.com/9655322/93087767-51248b00-f699-11ea-9437-a4224dac16c0.png The same needs to be done for the symmetric case.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/stevenhalim/cpbook-code/issues/77, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABIDWOBLOM3Y3IKABGKDYULSFYHE7ANCNFSM4RLSEPZA .

[vanHavel]

Hi, do you have time to take another look at this?

[stevenhalim]

Hi @vanHavel You are right. I totally missed this until someone else reported the same issue today (22 Jul 2024). Will fix it soon.