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-tree 中删除的工作原理，我只想对这段代码的复杂性说几句话。当然它是渐近最优的 O(log n)，但常数不是最好的。您可以将 _extractmin 和 _min 的调用替换为一个函数。这将通过返回一对两个指针（最小值和平衡结果）一次完成。

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 回答