Skew heap에 대한 방법을 제거 하시겠습니까?

Question

Skew 힙 클래스를 만들려고하지만 힙에서 요소를 제거하는 데 문제가 있습니다. 제거 기능은 코드의 끝에 있습니다. 논리가 옳은 것 같습니다. 요소를 찾아 자녀를 병합합니다. 제안 사항이 있습니까?

struct node{ 
    int key; 
    node* left; 
    node* right; 
}; 

class skewHeap{ 
public: 
    skewHeap(int k); 
    ~skewHeap(); 
    skewHeap& operator=(const skewHeap&); 
    node* merge(node* a,node* b); 
    void remove(node* a,int k); 
    void add(int k); 
    void print(node*) const; 
    node* getRoot(); 
private: 
    node* root; 
    void del(node* n){ 
     if(n == NULL) return; 
     else{ 
     del(n->left); 
     del(n->right); 
     delete n; 
     } 
    } 

    node* copy(node* n){ 
     if(n == NULL) return NULL; 
     node* tmp = new node; 
     tmp->key = n ->key; 
     tmp->left = copy(n->left); 
     tmp->right = copy(n->right); 
       return tmp; 
    } 


}; 

skewHeap::skewHeap(int k){ 
    root = new node; 
    root->key = k; 
    root->left = NULL; 
    root->right = NULL; 
} 

skewHeap::~skewHeap(){ 
    del(root); 
} 

skewHeap& skewHeap::operator=(const skewHeap& n){ 
    if(this != &n){ 
     del(root); 
     root = n.root; 
     copy(root); 
    } 
    return *this; 
} 

node* skewHeap::merge(node* a,node* b){ 
    if(a == NULL) return b; 
    if(b == NULL) return a; 
    else { 
     if(a->key > b->key){ 
      node* tmp = a; 
      a = b; 
      b = tmp; 
     } 
     node* tmp = a->right; 
     a->right = a->left; 
     a->left = merge(b,tmp); 
    } 
    return a; 
} 



void skewHeap::add(int k){ 
    node* p = new node; 
    p->key = k; 
    p->left = NULL; 
    p->right = NULL; 
    root = merge(root,p); 
} 

void skewHeap::print(node* n) const{ 
    if(n == NULL) return; 
    else{ 
     print(n->left); 
     cout<<n->key<<" "; 
     print(n->right); 
    } 
} 

node* skewHeap::getRoot(){ 
    return root; 
} 

void skewHeap::remove(node* n,int k){ 
    if(n == NULL) return; 
    if(n->key == k) { 
     n = merge(n->left,n->right); 
     return; 
     } 
    remove(n->left,k); 
    remove(n->right,k); 
} 

Answer 1

이 잘 작동

node* skewHeap::remove(node* n,int k){ 
    if(n == NULL) return NULL; 

    if(n->left && n->left->key == k) { 
     n->left = merge(n->left->left,n->left->right); 
     return n; 
    } 
    if(n->right && n->right->key == k) { 
     n->right = merge(n->right->left,n->right->right); 

     return n; 
     } 
    remove(n->left,k); 
    remove(n->right,k); 
}