更新AVL树代码来执行查找或插入

Question

我想在特定的算法中使用AVL树。我正在制作一个R包，所以我想坚持使用C或C++实现（目前使用C实现）。

我从AVL树实现基本代码：http://www.geeksforgeeks.org/avl-tree-set-2-deletion/

我试图做出将插入一个新的节点，如果关键是不是在树中的新功能，否则，如果它是在树，让我访问该节点，以便我可以查看它。我是一个noobie C程序员，但我遇到了一些困难。

这是我目前的实施。在主要功能中，我插入几个键并打印预购单以检查插入是否正常工作（它们是这样做的）。然后我尝试插入已经在树中的密钥。这导致了赛格故障:(有人可以帮助我走出这可能只是一个简单的问题，我的C：？

struct node* specialInsert(struct node* root, struct node* result, int *numBefore, int key, bool *flag){ 
    //We are inserting a new (non-root) node! 
    if (root == NULL){ 
     struct node* res = newNode(key); 
     res->equalCount = key; 
     *numBefore = 0; 
     *flag = true; 
     return(res); 
    }else if(key == root->key){ 
     *flag = false; 
     *numBefore = root->leftCount; 
     root->equalCount = root->equalCount + key; 

     if(result == NULL){ 
      struct node* result = newNode(root->key); 
     } 

     //printf("result key is: %d\n", result->key); 

     return root; 
    }else if(key < root->key){ 
     root->left = specialInsert(root->left, result, numBefore, key, flag); 
     root->leftCount = root->leftCount + key; 
     //if(*flag) update(root, key); 
     //else return(root->left); 
     update(root,key); 
    } else if(key > root->key){ 
     root->right = specialInsert(root->right, result, numBefore, key, flag); 
     *numBefore = *numBefore + root->leftCount + root->equalCount; 
     root->rightCount = root->rightCount + key; 
     //if(*flag) update(root, key); 
     //else return(root->right); 
     update(root,key); 
    } 
} 
struct node* findOrInsert(struct node* root, struct node* result, int *numBefore, int key){ 
    bool *flag; 
    bool val = false; 
    flag = &val; 

    /* 1. Perform the normal BST rotation */ 
    if (root == NULL){ 
     struct node* res = newNode(key); 
     *numBefore = 0; 
     res->equalCount = key; 
     return(res); 
    } 
    else return(specialInsert(root, result, numBefore, key, flag)); 


} 

，并在主要功能我：

struct node *root2 = NULL; 
struct node *result = NULL; 

root2 = findOrInsert(root2, result, x, 9); 
root2 = findOrInsert(root2, result, x, 5); 
root2 = findOrInsert(root2, result, x, 10); 
root2 = findOrInsert(root2, result, x, 0); 
root2 = findOrInsert(root2, result, x, 6); 
root2 = findOrInsert(root2, result, x, 11); 
root2 = findOrInsert(root2, result, x, -1); 
root2 = findOrInsert(root2, result, x, 1); 
root2 = findOrInsert(root2, result, x, 2); 


preOrder(root2); 
printf("\n"); 

root2 = findOrInsert(root2, result, x, 9); 
printf("Number of elements less than %d: %d\n", result->key,result->leftCount); 

Answer 1

你可以简单地依赖于其他人编写的代码。

一种这样的实现是Boost implementation of AVL Trees你可以通过CRAN package BH，让你Boost头为R（和C++）使用轻松访问。

当然，您也可以津津乐道调试自己的数据结构，并且也有其优点。在这种情况下，gdb可能会有帮助...