CODEWITHSUNDEEP
c++algorithmtemplatesstruct
Rontogiannis Aristofanis
Rontogiannis Aristofanis

Reputation: 9063

Implementation of avl tree causing segmentation fault

I'm trying to implement an avl tree. Its the first time I that, so my code is full of bugs. For example, when I insert an element in the avl tree it causes segmentation fault. To be more specific, the first time I insert an element at the tree, it's OK, but the second inserting causes the runtime error. Here is my code:

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

Upvotes: 0

Views: 345

Answers (1)

another.anon.coward
another.anon.coward

Reputation: 11395

Posting comment as answer:
The possibly reason of crash is in balance method, when accessing l and r members of node. When you have only 2 nodes in the tree one of them is potentially NULL, so adding a NULL-check (like the way it has been done in method u maybe) might help.

Side note: For using scanf in the code you will need to include <cstdio>, or better yet you can make use of cin to read tmp.

Hope this helps!

Upvotes: 1

Related Questions