1

私は現在、avlツリーを実装しています。挿入手順を修正した後 、avlツリーから特定のノードを削除する別の手順を実装しました。しかし、私は本当に立ち往生しています。それがどのように機能するのか、どのように実装するのかがわからないというわけではありませんが、実装が非常に難しいと思っていたので、コードの複雑さと削除機能に本当に気を配っています。誰かが私にavlツリーでの削除関数の短くて理解しやすい実装を教えてもらえますか？

これまでの私のコードは次のとおりです。

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;

  int h( node *x ) { return ( x?x->h:0 ); }

  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( h( x->l ) > 1 + h( x->r ) ) {
      if( h( x->l->l ) < ( x->l?h( x->l->r ):0 ) )  x->l = rotl( x->l );
      x = rotr( x );
    } else if( h( x->r ) > 1 + h( x->l ) ) {
      if( h( x->r->r ) < ( x->r?h( x->r->l ): 0 ) ) 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 ) ) { t->l = _insert( t->l, k ); }
    else { t->r = _insert( t->r, k ); }
    return balance( t );
  }
  void _inorder( node *t ) {
    if( t ) {
      _inorder( t->l );
      std::cout << t->key << " ";
      _inorder( t->r );
    }
  }
  node* _find( node *t, key_t k ) {
    if( !t ) return t;
    if( cmp( t->key, k ) ) return _find( t->l, k );
    else if( cmp( k, t->key ) ) return _find( t->r, k );
    else return t;
  }
  node* _min( node *t ) {
    if( !t || !t->l ) return t;
    else return _min( t->l );
  }
  node* _max( node *t ) {
    if( !t || !t->r ) return t;
    else return _max( t->r );
  }
public:
  avl_tree() : root( 0 ) {}

  void insert( key_t k ) { root = _insert( root, k ); }
  void inorder() { _inorder( root ); }
  node* find( key_t k ) { return _find( root, k ); }
  node* min() { return _min( root ); }
  node* max() { return _max( root ); }
};
4

1 に答える 1

1

したがって、AVL ツリーからの削除がどのように機能するかを理解していれば、このコードの複雑さについて簡単に説明したいと思います。もちろん、それは漸近的に最適な O(log n) ですが、定数は最適ではありません。_extractmin と _min の呼び出しを 1 つの関数に置き換えることができます。これは、2 つのポインターのペア (最小値とバランスの結果) を返すことにより、1 つのパスで機​​能します。

node* _extractmin( node *t ) {
    if ( !t->l ) return t->r;
    t->l = _extractmin(t->l);
    return balance(t);
}

node* _remove( node *t, key_t k )
{
    if ( !t ) return t;

    if (cmp(k, t->key)) 
        t->l = _remove(t->l, k);
    else if (cmp(t->key, k)) 
        t->r = _remove(t->r, k);
    else
    {
        node *l = t->l;
        node *r = t->r;
        delete t;
        if ( !r ) return l;
        node *m = _min(r);
        m->r = _extractmin(r);
        m->l = l;
        return balance(m);
    }
    return balance(t);
}

void remove( key_t k ) { root = _remove( root, k ); }
于 2012-12-15T11:33:14.377 に答える