Сбой LeftRotate в дереве AVL в последней точке при вводе чисел от 1 до 10 - PullRequest
Новая
       14

Сбой LeftRotate в дереве AVL в последней точке при вводе чисел от 1 до 10

0 голосов
/ 28 марта 2019

Я пытаюсь добавить числа в дереве AVL, где принимает узел (ключ, значение).При вводе чисел от (0,0) до (10,10) в цикле for происходит сбой кода при попытке ввода числа (10,10).

Ниже приведен код для вставки узлав дереве: 

int insert_in_tree_q5(struct AVLTreeNode **node, int key, int value){

    //AVLTreeNode *newNode = newAVLTreeNode(key, value);
    // if the tree is empty
    if(*node == NULL){
        *node = newAVLTreeNode(key, value);
    }
    if(key != (*node)->key){
        // insert on left if the data in the key is less than the data in the node.
        if (key<(*node)->key){
            insert_in_tree_q5(&(*node)->left, key,value);
        }
        // insert on right if the data in the key is greater than the data in the node.
        else if(key>(*node)->key)
        {
            insert_in_tree_q5(&(*node)->right, key,value);
        }
        // Update height of the ancestor node
        (*node)->height = 1 + max(height((*node)->left), height((*node)->right));
        // check balance to see if this node became unbalanced
        int balance = getBalance(*node);

        //First case to balance the unbalanced node
        // Left Left case
        if(balance>1 && key<(*node)->left->key){
            *node = rightRotate(*node);
        }
        // Right Right Case
        if (balance < -1 && key > (*node)->right->key)
            *node = leftRotate(*node);

        // Left Right Case
        if (balance > 1 && key > (*node)->left->key)
        {
            (*node)->left =  leftRotate((*node)->left);
            *node = rightRotate(*node);
        }

        // Right Left Case
        if (balance < -1 && key < (*node)->right->key)
        {
            (*node)->right = rightRotate((*node)->right);
            *node = leftRotate(*node);
        }
    }
    else if(key == (*node)->key){
        if (value<(*node)->value){
            insert_in_tree_q5(&(*node)->left, key,value);
        }
        // insert on right if the data in the key is greater than the data in the node.
        else if(value>(*node)->value)
        {
            insert_in_tree_q5(&(*node)->right, key,value);
        }
        // Update height of the ancestor node
        (*node)->height = 1 + max(height((*node)->left), height((*node)->right));
        // check balance to see if this node became unbalanced
        int balance = getBalance(*node);

        //First case to balance the unbalanced node
        // Left Left case
        if(balance>1 && value<(*node)->left->value){
            *node =rightRotate(*node);
        }
        // Right Right Case
        if (balance < -1 && value > (*node)->right->value)
            *node =leftRotate(*node);

        // Left Right Case
        if (balance > 1 && value > (*node)->left->value)
        {
            (*node)->left =  leftRotate((*node)->left);
            *node =rightRotate(*node);
        }

        // Right Left Case
        if (balance < -1 && value < (*node)->right->value)
        {
            (*node)->right = rightRotate((*node)->right);
            *node =leftRotate(*node);
        }
    }else if(key == (*node)->key && value == (*node)->value){
        return 0;
    }
    return 1;

}

Код для левого поворота: 

struct AVLTreeNode* leftRotate(struct AVLTreeNode *x){
    struct AVLTreeNode *y = x->right;
    struct AVLTreeNode *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;

    // Return new root
    return y;
}

Способ ввода значений в дереве: 

int InsertNode(AVLTree *T, int k, int v)
{
    //put your code here
    int returnedValue = insert_in_tree_q5(&T->root, k, v);
    if(returnedValue==0){
        return 0;
    }
    return 1;
}
tree4=newAVLTree();
    j=InsertNode(tree4, 10, 10);
    for (i=0; i<15; i++)
    {
        j=InsertNode(tree4, i, i);
        if (j==0) printf("(%d, %d) already exists\n", i, i);
    }

Подпись AVLTreeNode и AVLTree: 

typedef struct AVLTreeNode {
    int key; //key of this item
    int  value;  //value (int) of this item
    int height; //height of the subtree rooted at this node
    struct AVLTreeNode *parent; //pointer to parent
    struct AVLTreeNode *left; //pointer to left child
    struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;

AVLTree *newAVLTree()
{
    AVLTree *T;
    T = malloc(sizeof (AVLTree));
    assert (T != NULL);
    T->size = 0;
    T->root = NULL;
    return T;
}

PS: Если элемент (k, v) уже существует, он должен вернуть 0, добавить его в дерево и вернуть 1. Любые идеи относительно того, почемуон принимает все значения до (9,9), но завершается с ошибкой в ​​(10,10) с ошибкой «Поток 1: EXC_BAD_ACCESS (code = 1, address = 0x18)»

1 Ответ

0 голосов
/ 28 марта 2019

Если элемент (k, v) уже существует, он должен вернуть 0, иначе добавить его в дерево и вернуть 1

в insert_in_tree_q5, что вы делаете: 

if(*node == NULL){
    *node = newAVLTreeNode(key, value);
}
if(key != (*node)->key){
  ...CASE A
}
else if(key == (*node)->key){
    ...CASE B
} else if(key == (*node)->key && value == (*node)->value){
    return 0;
}
return 1;

дело else if(key == (*node)->key && value == (*node)->value) никогда не достигается, потому что непосредственно перед тем, как вы сделаете else if(key == (*node)->key), вам нужно изменить их порядок.

Для меня, когда (*node == NULL) вам не нужно продолжать тоже

Обратите внимание, что вы уже знаете, что if(key != (*node)->key) неверно, поэтому проверка равенства в двух следующих тестах бесполезна

Наконец, ваш код должен быть: 

if(*node == NULL){
    *node = newAVLTreeNode(key, value);
}
else if(key != (*node)->key){
  ...CASE A
}
else if( value == (*node)->value){
    return 0;
}
else {
    ...CASE B
} 
return 1;

В 

int InsertNode(AVLTree *T, int k, int v)
{
    //put your code here
    int returnedValue = insert_in_tree_q5(&T->root, k, v);
    if(returnedValue==0){
        return 0;
    }
    return 1;
}

, поскольку insert_in_tree_q5 возвращает только 0 или 1 InsertNode можно упростить до 

int InsertNode(AVLTree *T, int k, int v)
{
    return insert_in_tree_q5(&T->root, k, v);
}
...