세분화 오류를 일으키는 avl 트리 구현

Question

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; 
} 

Answer 1

게시 코멘트 : 여기 내 코드입니다
충돌의 가능성이있는 이유는 balance 방법이다, l 및 r 구성원에 node에 액세스 할 때 트리에 노드가 2 개인 경우 그 중 하나는 NULL 일 수 있으므로 NULL -check을 추가하면 (u과 같은 방식으로) 도움이 될 수 있습니다.

사이드 참고 : 코드에서 scanf을 사용하기 위해 당신은 <cstdio>, 또는 더 나은 아직 당신이 cin의 사용 tmp을 읽을 수 있도록 수를 포함해야합니다.

희망이 도움이됩니다.