0

我正在尝试实现一个 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 ); }
};

主文件

#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

发表评论作为答案：
崩溃的可能原因在于balance方法，当访问l和r成员时node。当树中只有 2 个节点时，其中一个是可能的NULL，因此添加NULL-check（就像在方法中完成的方式一样u）可能会有所帮助。

旁注：要scanf在代码中使用，您需要包含<cstdio>，或者更好的是，您可以使用cinto read tmp。

希望这可以帮助！

于 2012-12-15T08:36:41.723 回答