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의 호출을 하나의 함수로 바꿀 수 있습니다. 그것은 두 개의 포인터 (min과 balance 결과)를 반환함으로써 한 패스에서 작동합니다.

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