更新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可能會有幫助...