#help please

12 messages · Page 1 of 1 (latest)

iron lion
#

i have written a binary tree program that can insert, delete and display the avl tree. it works fine but when i delete and element the program does not proform a rotation and i dont know why.

{
    if (tree == NULL) {
        *ht_dec = FALSE; 
        return NULL;
    }

    switch (tree->balance)
    {
    case 0:
        tree->balance = 1;
        *ht_dec = FALSE;
        break;
    case -1:
        tree->balance = 0;
        break;
    case 1:
        if (tree->left != NULL && (tree->left->balance == 0 || tree->left->balance == 1))
        {
            struct node *leftChild = tree->left;
            tree->left = leftChild->right;
            leftChild->right = tree;
            tree->balance = 0;
            tree = leftChild;
            *ht_dec = TRUE;
        }
        else if (tree->left != NULL && tree->left->right != NULL) 
        {
            struct node *leftChild = tree->left;
            struct node *rightGrandChild = leftChild->right;
            leftChild->right = rightGrandChild->left;
            rightGrandChild->left = leftChild;
            tree->left = rightGrandChild->right;
            rightGrandChild->right = tree;
            if (rightGrandChild->balance == 1)
                tree->balance = -1;
            else
                tree->balance = 0;
            if (rightGrandChild->balance == -1)
                leftChild->balance = 1;
            else
                leftChild->balance = 0;
            rightGrandChild->balance = 0;
            tree = rightGrandChild;
            *ht_dec = TRUE;
        }
        else {
            *ht_dec = FALSE; 
        }
        break;
    }

    return tree;
}``` i am guessing the porblem lies here
knotty timberBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

iron lion
# 
{
    if (tree == NULL) {
        *ht_dec = FALSE; 
        return NULL;
    }

    switch (tree->balance)
    {
    case 0:
        tree->balance = -1;
        *ht_dec = FALSE;
        break;
    case 1:
        tree->balance = 0;
        break;
    case -1:
        if (tree->right != NULL && (tree->right->balance == 0 || tree->right->balance == -1))
        {
            struct node *rightChild = tree->right;
            tree->right = rightChild->left;
            rightChild->left = tree;
            tree->balance = 0;
            tree = rightChild;
            *ht_dec = TRUE;
        }
        else if (tree->right != NULL && tree->right->left != NULL) 
        {
            struct node *rightChild = tree->right;
            struct node *leftGrandChild = rightChild->left;
            rightChild->left = leftGrandChild->right;
            leftGrandChild->right = rightChild;
            tree->right = leftGrandChild->left;
            leftGrandChild->left = tree;
            if (leftGrandChild->balance == -1)
                tree->balance = 1;
            else
                tree->balance = 0;
            if (leftGrandChild->balance == 1)
                rightChild->balance = -1;
            else
                rightChild->balance = 0;
            leftGrandChild->balance = 0;
            tree = leftGrandChild;
            *ht_dec = TRUE;
        }
        else {
            *ht_dec = FALSE; 
        }
        break;
    }

    return tree;
}```this is the right one as well
knotty timberBOT
#

This question is being automatically marked as stale.
If your question has been answered, type !solved.
If your question is not answered feel free to bump the post or re-ask.
Take a look at !howto ask for tips on improving your question.

iron lion
# 
{
    struct node *tmp;
    if (tree == NULL)
    {
        printf("Data not found\n");
        *ht_dec = FALSE;
    }
    else if (data < tree->data)
    {
        tree->left = delete(data, tree->left, ht_dec);
        if (*ht_dec == TRUE)
            tree = del_left_balance(tree, ht_dec);
    }
    else if (data > tree->data)
    {
        tree->right = delete(data, tree->right, ht_dec);
        if (*ht_dec == TRUE)
            tree = del_right_balance(tree, ht_dec);
    }
    else
    {
        if (tree->left != NULL && tree->right != NULL)
        {
            tmp = findLargestElement(tree->left);
            tree->data = tmp->data;
            tree->left = delete(tree->data, tree->left, ht_dec);
            if (*ht_dec == TRUE)
                tree = del_left_balance(tree, ht_dec);
        }
        else
        {
            tmp = tree;
            if (tree->left == NULL)
                tree = tree->right;
            else if (tree->right == NULL)
                tree = tree->left;
            free(tmp);
            *ht_dec = TRUE;
        }

        if (*ht_dec == TRUE)
        {
            if (tree != NULL)
            {
                if (tree->balance == 0)
                {
                    printf("R0 rotation.\n");
                }
                else if (tree->balance == 1)
                {
                    printf("R-1 rotation.\n");
                }
                else if (tree->balance == -1)
                {
                    printf("R1 rotation.\n");
                }
                tree->balance = 0;
                *ht_dec = FALSE;
            }
        }
    }
    return tree;
}``` this is the delete function it works correctly for my first test case but not for the second one and i dont know why, when i put in 65, 63, 54, 51, 47, 45, 39, 18 and then delete 65 it should say rotation R0 but it says rotation R1
umbral mauve
iron lion
# 

   65
  63
   54
 51
   47
  45
   39
    18

Inorder Traversal is :  18 39 45 47 51 54 63 65
1.Insert
2.Delete
3.Display
4.Find largest element
5.Quit
Enter your option : 2
Enter the value to be deleted : 65
R-1 rotation.``` yes of course this is the second example that is supposed to preform a R0 rotation but instead it does a R-1 rotation
umbral mauve
#

So, that would be a 'no' apparently.

#

I see no code that directly sets tree->balance, other than tree-balance = 0, so it is hard to know.

iron lion
# 
{
    bool ht_inc;
    int data, num;
    struct node *root = NULL;
    while (1)
    {
        printf("1.Insert\n");
        printf("2.Delete\n");
        printf("3.Display\n");
        printf("4.Find largest element\n");
        printf("5.Quit\n");
        printf("Enter your option : ");
        scanf("%d", &num);
        switch (num)
        {
        case 1:
            printf("Enter the value to be inserted : ");
            scanf("%d", &data);
            if (search(root, data) == NULL)
                root = insert(data, root, &ht_inc);
            else
                printf("Duplicate value ignored\n");
            break;
        case 2:
            if (root == NULL)
            {
                printf("Tree is empty\n");
                continue;
            }
            printf("Enter the value to be deleted : ");
            scanf("%d", &data);
            root = delete (data, root, &ht_inc);
            if (ht_inc == TRUE)
            {
                printf("R1 rotation.\n");
            }
            else if (ht_inc == FALSE)
            {
                printf("R-1 rotation.\n"); // Perform R0 rotation when height doesn't change
            }
            else if (ht_inc == 0)
            {
                printf("R0 rotation.\n");
            }
            break;
        case 3:
            if (root == NULL)
            {
                printf("Tree is empty\n");
                continue;
            }
            printf("Tree is :\n");
            display(root, 1);
            printf("\n\n");
            printf("Inorder Traversal is : ");
            inorder(root);
            printf("\n");
            break;
        case 4:
            if (root == NULL)
           {
            printf("Tree is empty\n");
            continue;
         }
        printf("Largest element in the tree is: %d\n", findLargestElement(root)->data);
        break;
   case 5:
      exit(1);
  default:
     printf("Wrong option\n");
  }
 }
    return 0;
}```
#

i changed the main too but it still preforms R-1 rotation for both the test cases

iron lion
#

!solved