在avl树中执行删除程序

Question

我目前正在实施avl树。在纠正insertion procedure之后，我开始执行另一个过程，从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); } 
}; 

Answer 1

因此，如果您了解如何从AVL树作品的缺失，我只想说这个代码的复杂性几句话。当然，它是渐近最优的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); }