刪除傾斜堆的方法？

Question

我想創建傾斜堆類，但我有一個從堆中刪除元素的問題.Remove函數是在代碼的末尾。邏輯似乎是正確的。找到元素併合並它的children.Any建議？

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