avl樹導致分段錯誤的實現

我試圖實現avl樹。這是我第一次，所以我的代碼充滿了錯誤。例如，當我在avl樹中插入元素時，會導致分段錯誤。更具體地說，我第一次在樹上插入一個元素時，沒問題，但第二次插入會導致運行時錯誤。這裏是我的代碼：avl樹導致分段錯誤的實現

avl_tree.hpp

template< class key_t, class compare_t=std::less<key_t> > 
struct avl_tree { 
private: 
    struct node { 
    node *l, *r; 
    int h, size; 
    key_t key; 
    node(key_t k) : l(0), r(0), h(1), size(1), key(k) {} 
    void u() { 
     h=1+std::max((l?l->h:0), (r?r->h:0)); 
     size=(l?l->size:0) + (r?r->size:0) + 1; 
    } 
    } *root; 
    compare_t cmp; 

    node* rotl(node *x) { 
    node *y=x->r; 
    x->r=y->l; 
    y->l=x; 
    x->u(); y->u(); 
    return y; 
    } 
    node* rotr(node *x) { 
    node *y=x->l; 
    x->l=y->r; 
    y->r=x; 
    x->u(); y->u(); 
    return y; 
    } 
    node* balance(node *x) { 
    x->u(); 
    if(x->l->h > 1 + x->r->h) { 
     if(x->l->l->h < x->l->r->h) x->l = rotl(x->l); 
     x = rotr(x); 
    } else if(x->r->h > 1 + x->l->h) { 
     if(x->r->r->h < x->r->l->h) x->r = rotr(x->r); 
     x = rotl(x); 
    } 
    return x; 
    } 
    node* _insert(node *t, key_t k) { 
    if(t==NULL) return new node(k); 
    if(cmp(k, t->key)) { std::cout<<"going left."<<std::endl; t->l = _insert(t->l, k); } 
    else { std::cout<<"going right."<<std::endl; t->r = _insert(t->r, k); } 
    std::cout << "calling balance." << std::endl; 
    return balance(t); 
    } 
    void _inorder(node *t) { 
    if(t) { 
     _inorder(t->l); 
     std::cout << t->key << " "; 
     _inorder(t->r); 
    } 
    } 
public: 
    avl_tree() : root(0) {} 

    void insert(key_t k) { 
    root = _insert(root, k); 
    } 
    void inorder() { _inorder(root); } 
};

main.cpp中爲回答

#include <iostream> 
#include "avl_tree.hpp" 

using namespace std; 

int main() { 
    avl_tree<int> avl; 
    for(int i=0; i<5; ++i) { 
    int tmp; 
    scanf("%d", &tmp); 
    avl.insert(tmp); 
    } 
    avl.inorder(); 

    return 0; 
}

來源

2012-12-15 Rontogiannis Aristofanis

可能問題出在'balance'中，當你在樹中只有2個節點時，你正在訪問'l'和'r'，所以它們中的一個肯定是'NULL'。添加一個NULL檢查，看看它是否有幫助 –

@ another.anon.coward擊敗了我，並應該發表評論作爲答案。 – Beta

@貝塔：當然！ :) –

發帖評論：
的可能原因墜毀的是balance方法，當訪問node的l和r成員時。當樹中只有2個節點時，其中一個節點可能爲NULL，因此添加NULL -check（可能與方法u中的方法相似）可能會有所幫助。

邊注：在代碼中使用scanf您將需要包括<cstdio>，或更好，但你可以利用cin閱讀tmp。

希望這會有所幫助！

來源

2012-12-15 08:36:41

avl樹導致分段錯誤的實現

回答

相關問題