0

avl ツリーを実装しようとしています。初めてのことなので、私のコードはバグだらけです。たとえば、avl ツリーに要素を挿入すると、セグメンテーション違反が発生します。具体的に言うと、最初にツリーに要素を挿入するときは問題ありませんが、2 回目の挿入で実行時エラーが発生します。これが私のコードです：

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

1 に答える 1

1

コメントを回答として投稿:のメンバーにアクセスするとき、
クラッシュの原因として考えられるのはメソッドにあります。ツリーにノードが 2 つしかない場合、そのうちの 1 つが潜在的に. balancelrnodeNULLNULLu

補足: コードで使用するには、scanfを含める必要があります。 <cstdio>cintmp

お役に立てれば！

于 2012-12-15T08:36:41.723 に答える